|
|
|
|
|
|
|
sorted; each value is put into its proper place as it is read. We develop this sorting technique in the Exam Attendance case study at the end of this chapter. |
|
|
|
|
|
|
|
|
Binary Search in an Ordered List |
|
|
|
|
|
|
|
|
There is a second search algorithm on a sorted list that is considerably faster both for finding an item and for discovering that an item is missing. This algorithm is called a binary search. A binary search is based on the principle of successive approximation. The algorithm divides the list in half (divides by 2-that's why it's called binary search) and decides which half to look in next. Division of the selected portion of the list is repeated until the item is found or it is determined that the item is not in the list. |
|
|
|
|
|
|
|
|
This method is analogous to the way in which we look up a word in a dictionary. We open the dictionary in the middle and compare the word with one on the page that we turned to. If the word we're looking for comes before this word, we continue our search in the left-hand section of the dictionary. Otherwise, we continue in the right-hand section of the dictionary. We repeat this process until we find the word. If it is not there, we realize that either we have misspelled the word or our dictionary isn't complete. |
|
|
|
|
|
|
|
|
The algorithm for a binary search is given below. The list of values is called list, and the value being looked for is called item (see Figure 12-6). |
|
|
|
|
|
|
|
|
1. Compare item to list[middle]. If item = list[middle], then we have found it. If item < list[middle], then look in the first half of list. If item > list[middle], then look in the second half of list. |
|
|
|
|
|
|
|
|
2. Redefine list to be the half of list that we look in next, and repeat the process in Step 1. |
|
|
|
|
|
|
|
|
3. Stop when we have found item or know it is missing. We know it's missing when there is nowhere else to look and we still have not found it. |
|
|
|
|
|
|
|
|
This algorithm should make sense. With each comparison, at best, we find the item for which we are searching; at worst, we eliminate half of the remaining list from consideration. |
|
|
|
|
|
|
|
|
Figure 12-6
Binary Search |
|
|
|
|
|
