DSA Searching: Linear and Binary Search

Searching means finding where an item is in a collection, or learning that it is not there.

Linear Search

Linear search checks each item from the start until it finds the target. It works on any list, sorted or not.

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

rolls = [104, 87, 233, 56, 190]
print(linear_search(rolls, 56))
print(linear_search(rolls, 999))

3
-1

Returning -1 is a common way to say "not found".

• Best case: the item is first, O(1)
• Worst case: the item is last or missing, O(n)

Binary Search

Binary search only works on a sorted list, but it is much faster. It is like finding a word in a dictionary: open in the middle, see if your word comes before or after, and throw away the other half.

Steps:

1. Look at the middle item.
2. If it is the target, you are done.
3. If the target is smaller, search the left half. If bigger, search the right half.
4. Repeat until found, or until no items are left.

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

prices = [50, 120, 180, 250, 400, 650, 900]
print(binary_search(prices, 400))
print(binary_search(prices, 50))
print(binary_search(prices, 300))

4
0
-1

Tracing Binary Search

Searching for 400 in the list above:

Each step halves the search space, so binary search is O(log n). A sorted list of one million items needs at most about 20 steps.

Recursive Binary Search

Binary search can also be written with recursion:

def bsearch(items, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if items[mid] == target:
        return mid
    if items[mid] < target:
        return bsearch(items, target, mid + 1, high)
    return bsearch(items, target, low, mid - 1)

data = [3, 9, 14, 27, 31, 48]
print(bsearch(data, 27, 0, len(data) - 1))

3

Python's Built-in Tools

• x in items and items.index(x) do a linear search, O(n)
• The bisect module does binary search on sorted lists
• A set or dict finds keys in O(1) on average

Comparison

Exercise