Searching: Linear Search and Binary Search

Finding things in a list

Searching is the first real algorithm most people meet, and it is a good one, because the two standard methods differ enormously in cost and the reason why is easy to see.

The problem: given a collection and a target value, find where the target is — or report that it is not there.

Linear search

Start at the beginning. Check each element. Stop when you find it or run out.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i          # found - return the position
    return -1                 # not found

roll_numbers = [17, 4, 23, 8, 42, 15, 9]

print("Searching for 42:", linear_search(roll_numbers, 42))
print("Searching for 17:", linear_search(roll_numbers, 17))
print("Searching for 99:", linear_search(roll_numbers, 99))

That is the whole algorithm. Returning -1 for "not found" is a convention — any value that cannot be a valid index works.

Cost. Best case the target is first: 1 comparison, O(1). Worst case it is last or absent: n comparisons, O(n). Average, about n/2, which is still O(n).

Space. O(1). It only needs the loop index.

Linear search has one large advantage that gets overlooked: it works on any list, in any order, always. No preparation required.

Binary search

Now suppose the list is sorted. Sorted data gives you information you did not have before: if the middle element is too small, every element before it is also too small.

The method:

1. Look at the middle element.
2. If it equals the target, done.
3. If it is smaller than the target, throw away the left half and repeat on the right.
4. If it is larger, throw away the right half and repeat on the left.

Every step removes half of what is left. That is the whole trick.

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

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1     # target must be in the right half
        else:
            high = mid - 1    # target must be in the left half

    return -1

sorted_marks = [12, 25, 33, 41, 58, 64, 79, 88, 91]

print("Search 58:", binary_search(sorted_marks, 58))
print("Search 12:", binary_search(sorted_marks, 12))
print("Search 91:", binary_search(sorted_marks, 91))
print("Search 50:", binary_search(sorted_marks, 50))

Why it is O(log n)

Start with n elements. After one comparison you have n/2 left, then n/4, then n/8. How many halvings until you reach 1?

That count is log base 2 of n.

• 1,000 items: about 10 comparisons
• 10,00,000 items: about 20 comparisons
• 100 crore items: about 30 comparisons

A thousand-fold increase in data costs you ten extra comparisons. This is why binary search feels almost magical the first time you trace it by hand.

When binary search is actually valid

This is where people get burned. Binary search needs all of the following:

The data must be sorted by the same key you are searching on. A list sorted by name is useless for searching by marks.

You need O(1) random access. Binary search jumps to the middle. On an array that is free; on a linked list, reaching the middle costs O(n), which destroys the benefit entirely.

The comparison must be consistent. If a < b and b < c then a < c must hold. Ordinary numbers and strings satisfy this.

Also think about whether sorting first is worth it. Sorting costs O(n log n). If you are going to search once, sorting then binary searching is O(n log n) — slower than just doing one O(n) linear scan. Sorting pays off when you search many times on the same data.

Sort once, search a thousand times: sorting wins. Search once: don't bother sorting.

The off-by-one traps

Binary search is famously short and famously easy to get wrong. Here are the exact places it breaks.

Trap 1: high initialised to len(arr) instead of len(arr) - 1. With low <= high as the loop condition, mid can then land on an index that does not exist. Keep high = len(arr) - 1 paired with low <= high.

Trap 2: while low < high instead of low <= high. When the range shrinks to one element, low equals high. With < the loop exits before checking that final element, so a target sitting there is reported missing.

Trap 3: forgetting the + 1 and - 1. Writing low = mid instead of low = mid + 1 means the range sometimes does not shrink, and the loop runs forever. You already checked mid, so exclude it.

Trap 4: searching unsorted data. No error is raised. You just get wrong answers, sometimes correct by luck, which makes it hard to spot.

Here is a version that reports what it does, so you can watch the range shrink:

def binary_search_traced(arr, target):
    low, high = 0, len(arr) - 1
    step = 0

    while low <= high:
        step += 1
        mid = (low + high) // 2
        print("step", step, "- range [", low, ",", high, "] mid index", mid,
              "value", arr[mid])
        if arr[mid] == target:
            print("Found", target, "at index", mid, "in", step, "steps")
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    print(target, "not found after", step, "steps")
    return -1

data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print("List has", len(data), "items")
binary_search_traced(data, 23)
print()
binary_search_traced(data, 40)

Ten items, found in at most four steps. Trace it on paper once — that is worth more than reading it three times.

Common mistakes

Running binary search on unsorted data. It fails silently. Sort first, or check that your data is genuinely sorted.

Using low <= high with high = len(arr). Mismatched bounds cause IndexError or infinite loops. Pick one convention and stay with it.

Not shrinking the range. low = mid or high = mid without the offset can leave the range unchanged and hang the program.

Returning a boolean when you needed the index. "Is it there?" and "where is it?" are different questions. Decide which one your function answers.

Assuming binary search finds the first occurrence. With duplicates it returns some matching index, not necessarily the earliest. Finding the first occurrence needs a small modification: on a match, record it and keep searching left.

Practice

Try the searching exercises on the practice page — write binary search from memory before checking it.