Searching   Searching is the process by which a specific element is located within a collection of elements (such as an array). Operation of locating a data element. Search method is based on: Speed vs. space Often the faster method utilizes more space.

Binary Search Binary search consists of binary decisions with two choices.  Binary Search Example: Say you were looking for the 'Malibu Technologies' in a telephone directory.  If you 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 begin with the letter L.   Then you decide whether to continue looking for 'Malibu Technologies' to the left or to the right of this page.  By doing so you have reduced your search by half of the telephone directory.    Conducting a binary search as in the example above requires that the list that you are working with be sorted.  How does a binary search 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 member that is in between the bottom and the top points, 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 above sorted array.  

The value at the "mid" position is 17, which is less than 18.  Because of this we know that we can ignore all the values less before 17.  

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 at last!  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 the two between the sequential search and the binary search. 

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