Design a Search

🐢 The slow way: check one by one

Worst case: checks on this list.

1. Start at the first box.
2. Is this the number? If yes, done!
3. If not, move to the next box and ask again.
4. Keep going until you find it — or run out of boxes.

🐇 The smart way: split in half each time

Worst case: checks on this list.

1. Because the list is sorted, check the box in the exact middle.
2. Too big? The number must be to the left — forget the whole right half.
3. Too small? Forget the whole left half instead.
4. You've now got half as many boxes to search. Repeat the same trick on what's left.

🐢 Linear search

def linear_search(numbers, target):
    for index in range(len(numbers)):
        if numbers[index] == target:
            return index       # found it!
    return -1                  # never found it

🐇 Binary search

def binary_search(numbers, target):
    low = 0
    high = len(numbers) - 1

    while low <= high:
        middle = (low + high) // 2
        if numbers[middle] == target:
            return middle          # found it!
        elif numbers[middle] < target:
            low = middle + 1       # forget the left half
        else:
            high = middle - 1      # forget the right half

    return -1                      # never found it