CIS3355: Business Data Structures
Fall, 2008
 

9.2 Tutorial: Which search technique is better and why?  Sequential Search-->Binary Search-->9.2 Tutorial: Which search technique is better and why?  Sequential Search-->Binary Search-->

	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.
	Sequential Searches The sequential search is the easiest method for navigating through a list to locate a specific element. In a sequential search the search process is initiated by a request from the user to locate a specific element within our array.   The search for the element begins with a comparison of the user's request with the element in the first position of the array.   If there is no match, we then proceed to continue searching through the remaining positions within the array until we are successful in locating the element in the array which matches with the user's request.    The amount of time required to complete this task depends on the request from the user and the number of elements in the array.  This time can be greatly reduced if the array has been sorted.
	Binary Search 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 Sequential Searches (n+1)	Average Sequential Searches (n+1)/2	Maximum Binary Searches log2n	Average Binary Searches log2n-1
10	11	5.5	4	2.9
50	51	25.5	6	4.6
100	101	50.5	7	5.8
1,000	1,001	500.5	10	9.0
10,000	10,001	5,000.5	14	12.3
100,000	100,001	50,000.5	17	15.6
1,000,000	1,000,001	500,000.5	20	18.9
10,000,000	10,000,001	5,000,000.5	24	22.3

Table 9.3

Remember that as the number of elements to be searched continue to increase so will the number of comparisons needed.  The number of binary searches is considerably lower than the sequential searches.