Search Technique
Which Technique is better?
Sequential Searching or Binary Searches

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 Search

In finding the better technique to sort many types of data or elements the result may be time consuming and not necessarily the best or ideological approach. There are two methods in which we can gather or sort a list (small or long) of information: Sequential searches and Binary searches.

Sequential searching is the best method to look and locate a specific element in our array. In sequential search each element is searched until theelement is found and the end of the list is reached. The comparison begins at the user’s first position of the arrays or specific elements. Once the search begins if there is no specific match in the array then the search continues to search in the remaining positions of the array until the specified user search is complete. In sequential search each element is searched until the element is found and the end of the list is reached.

The sequential search is the easiest method for navigating through a list to locate a specific element. The amount of time required to complete this task depends on the request from the user and the number of elements in the array. The amount of time required to complete this task depends on the request from the user and the number of elements in the array.

Question:
True or False: If searching for a contained list that has more than 30-50 elements a sequential search is preferred.

Answer:
False, although the sequential search is easier to use the many number of elements would make the search real time longer and the elements would be complexed.

Binary Search

In Searching for a list of more than 30-50 elements it is more convenient to use the Binary Search method. 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.

Example: If we were to search in the sorted array for the number 19:

Offsets

The low point would be 1, and the top point would be 21, the mid point is offset 3: In finding the mid point we use the formula (bottom+top/2 = (0+6/2).

Since the offset 3 and the number is 19 the search stops because we have found the number in the midpoint. In binary search we continue the process until the corresponding number that we are looking for is the midpoint.

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 log₂n	Average Binary Searches log₂n-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 continues to increase so will the number of comparisons needed. The number of binary searches is considerably lower than the sequential searches.

Some good references would be:

1. Searching and Sorting. Chapter 9 Pkirs lecture notes

2. www.cs.sunysb.edu/~skienna/214/lecture/lect19lect19.html