Binary Search, A Closer Look A binary search is a technique for quickly locating an item in a sequential list, a sort of guessing game where the response is either, you're too high, you're too low, or that's the right one. Although a Binary search is the fastest approach, it requires a contiguous block of RAM for all its elements. The item or key you want is compared to the other data in the middle of a list that is organized in ascending or descending order. The half that contains the data is then compared to the data in the middle, and so on, either until the key is located, or a small enough group is isolated to be sequentially searched.   For Instance: Say you were looking for Mario's Pizzeria in a telephone book.  If you happened to open the directory at the mid point you would look at the top of the page and find that the businesses listed on this page began with the letter L.   Then you decide whether to continue looking for Mario's Pizzeria to the left or to the right of this page.  By doing so you have reduced your search by half of the telephone directory.      So how does a Binary Search really work? A binary search requires the use of two points: the bottom or "lo" which points to the lower section of the array and the top or "hi" which points to a higher section of the array. The binary search checks the value of the array element that is between the bottom and the top points, giving you the mid point. If the value at this location is less than the value we are searching for, then the mid point becomes the new bottom pointer.     Consider the following example:                1 5 7 9 10 13 17 18 23 25 27 33 39 ^           ^           ^ lo           mid           hi

In this example we are searching for the number 18 within the sorted array above.  

The value at the "mid" position is 17, which is less than 18. Now we know that we can ignore all the values before 17 because they are less than 18.  

The next step is to assign 18 as the new "lo" and then to determine the new mid-point of the array, 25. 

18	23	25	27	33	39
^		^			^
lo		mid			hi

This value is greater than 18, therefore 23 becomes the new "hi" point and 17 becomes the new "lo" point for our search.

17	18	23
^	^	^
lo	mid	hi

Success!  The new mid-point contains the value that we are searching for.

If at any point during our search process the value of our "lo" point becomes greater than the value of our "hi" point the search process is halted without a result. 

The following table allows you to compare a sequential search with a binary search and illustrates the number of searches each approach is capable of. 

Number of Elements in the Array	Maximum  Binary Searches log2n	Average Binary Searches log2n-1
10	4	2.9
50	6	4.6
100	7	5.8
1,000	10	9.0
10,000	14	12.3
100,000	17	15.6
1,000,000	20	18.9
10,000,000	24	22.3