In fact, for most
communities, a telephone book where the entries were not sorted alphabetically would be unthinkably inefficient!
If the list to be searched is already ordered from smallest to largest, the binary search algorithm can find
any entry in (lg n) time. If the list contains 1,000,000 entries, that means the binary search will locate the
item after reading fewer than 20 entries. The sequential search, on average, will have to read 500,000 entries.
What a difference!
The binary search works by repetitively dividing the list in half. It starts by comparing the element in the
middle of the list with the item sought. If the search item is smaller than the element in the middle of the list,
the binary search reads the element at the middle of the first half of the list. Then, if the search item is larger
than that element, the binary search next reads the element at the middle of the second half of the front half of
the list. Eventually, the search finds the element sought, or concludes that the element is not present in the list.
Here is pseudocode for a binary search:
BinarySearch(list, search_item)
begin <-- 1
end <-- length of list
match_found <-- false
// Repeat search as long as no match has been found
// and we have not searched the entire list.
Pages:
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68