Cacher is the code snippet organizer for pro developers

Binary Search

This is the method like tearing the phonbook in half and try to find a certain person.

There is a condition that must be true, or else we can't use this method: the array must be sorted. If the array is not sorted, we can't just eliminate the other half of the array because we are not sure if everything in there are all smaller or bigger than the middle point.

In pseudocode:

Repeat until the (sub)array is of size 0:
	Calculate the middle point of the current (sub)array
	If the target is at the middle, stop
	Otherwise, if the target is less than what's at the middle, repeat, changing the end point to be just to the left of the middle.
	Otherwise, if the target is greater than what's at the middle, repeat, changing the end point to be just to the right of the middle.

So, here we have 4 main variables for the whole program:

Target Number, Start Point of the sub-array, End Point of the sub-array, Middle Point of the sub-array.

The start, end, and middle point of the sub-array are changing all the time according to the search.

If the Target does exist in the array, we will be able to find it by running this algorithm.
If the Target does not exist in the array, we might end up having the End Point is before the Start Point, so the number for End is smaller than Start. That's when we know that we've searched the whole array and the Target doesn't exist in the array.

Because this method have to get array sorted first, it might be less effective depending on the size of the array.

Worst-case scenario: O(log n)
Best-case scenario: 1