Searching algorithms

Murad thinks of a number from 1 to 100, and Aysel has to find it. After each guess, Murad only says “higher”, “lower” or “correct”. If Aysel asks 1, 2, 3… in order, she might need 100 guesses. But if she starts at 50 and halves the range each time, she will find the number in at most 7 guesses. These two approaches are two famous algorithms: linear search and binary search.

Linear search

In linear (sequential) search, the items of a list are compared with the target one by one, starting from the first. When a match is found, the search stops; if we reach the end of the list without a match, the item is not there.

The advantage of linear search is that it is simple and works on any list, even an unsorted one. The drawback is speed: in the worst case, a list of n items needs n comparisons.

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

numbers = [7, 3, 23, 9, 15]
print(linear_search(numbers, 23))
print(linear_search(numbers, 4))

2
-1

Binary search

Binary search works only on a sorted list (for example, in increasing order), but it is very fast. At each step the target is compared with the middle item of the range, and half of the list is thrown away at once.

1. 1
   Find the middle

   Take the item in the middle of the current search range.

2. 2
   Compare

   If the middle item equals the target, it is found and the search is over.

3. 3
   Drop half

   If the target is smaller than the middle item, keep searching in the left half; if it is bigger, in the right half.

4. 4
   Repeat

   Repeat steps 1–3 until the item is found or the range is empty. An empty range means the item is not in the list.

def binary_search(items, target):
    low, high = 0, len(items) - 1
    steps = 0
    while low <= high:
        mid = (low + high) // 2
        steps += 1
        if items[mid] == target:
            return mid, steps
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1, steps

numbers = [3, 8, 12, 17, 23, 31, 37, 42, 50]
print(binary_search(numbers, 37))
print(binary_search(numbers, 5))

(6, 2)
(-1, 3)

Which one is faster?

In binary search every comparison halves the list, so doubling the list adds just one more comparison. For large lists the difference is amazing: