while match_found = false AND begin <= end
// Find the item at the midpoint of the list
midpoint <-- (begin + end) / 2
22 ALGORITHMS [CHAP. 2
// If it??™s the one we??™re looking for, we??™re done
if list[midpoint] = search_item
match_found = true
// If the search item is smaller, the next
// list item to check is in the first half
else if search_item < list[midpoint]
end <-- midpoint - 1
// Otherwise, the next list item to check
// is in the back half of the list
else
begin <-- midpoint + 1
// Return true or false, depending on whether we
// found the search_item
return match_found
With each iteration, the binary search reduces the size of the list to be searched by a factor of 2. So, the
binary search generally will find the search item, or conclude that the search item is not in the list, when the
algorithm has executed (lg n) iterations or fewer. If there are seven items in the list, the algorithm will complete
in three iterations or fewer. If there are 1,000,000 items in the list, the algorithm will complete in 20 iterations
or fewer.
If the original list happens to be a perfect power of 2, the maximum number of iterations of the binary
search can be 1 larger than (lg n). When the size of the list is a perfect power of 2, there are two items at the (lg n)
level, so one more iteration may be necessary in that circumstance.
Pages:
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69