02 Binary Search

1. Binary Search requires the data it is searching must be sorted. So you can only use the binary search algorithm on data that has been sorted.

   • If you want to use it to search an array and the array has not been sorted then you are going to have to sort it, the array first then you can use any of the sort algorithms that we have looked at to sort the array.

   • If you are searching on LinkedList then you are going to have to sort it first.

What is Binary Search?

1. It chooses the element in the middle of the array and compares it against the search value.

2. If the element is equal to the value, then we are done.

3. If the element is greater then the value, search the left half of the array.

4. If the element is less then the value, search the right half of the array.

At some point, there will be only one element in the partition you are checking, but it doesn

t have to get to that point.

It can be implemented recursively.

Time Complexity is O(logn) because it keeps dividing the array in the half.