Binary Search

Part of: Algorithms, Iteration & Simulation

Linear search checks every element. But if a list is already sorted , you can do dramatically better with binary search : the algorithm you use instinctively when looking up a word in a dictionary: open to the middle, decide which half holds your word, and repeat. The strategy: halve the search space Binary search keeps two pointers, lo and hi, marking the current search range. Each pass it looks at the middle element and discards half the remaining list: Each comparison has three outcomes: - Equal : found it; stop. - Middle too small : the target must be to the right, so move lo past mid. - Middle too big : the target must be to the left, so move hi before mid. When lo passes hi, the range is empty and the target is absent. Why it is so fast Every pass throws away half the remaining elements. A list of 1,000 items is cut to 500, 250, 125, ... reaching one element in only about 10 steps. In general binary search needs about log base 2 of n comparisons, for a million items, roughly 20 instead of a million. This is the difference between work proportional to n and work proportional to log n. The one requirement Binary search only works on a sorted list. On unsorted data the "which ha

Challenge: Binary Search Index