Searching: Linear and Binary Search

What “searching” means

Searching is the task of finding out whether a particular value is present in a collection, and if so, where it sits. The collection here is a list: an ordered sequence of items that Python writes with square brackets, like [4, 8, 15, 16, 23, 42]. Each item has a position number called an index, counted from 0. So in that list the value 4 is at index 0, and 42 is at index 5.

The value we are looking for is called the target. A search either returns the index where the target was found, or reports that it is not there.

Two facts control how fast a search can be:

• Whether the list is sorted (arranged in order, smallest to largest) or in no particular order.
• How many items the list has. We call that count n.

We measure cost with Big-O notation, a way of describing how the amount of work grows as n grows. O(n) means the work grows in step with the list size: double the list, double the work. O(log n) means the work grows very slowly: double the list, and the work goes up by just one more step. The log here is the base-2 logarithm, which answers “how many times can I halve n before I reach 1?” For a million items that is about 20.

Linear search

Linear search is the direct method: start at the first item and look at each one in turn until you find the target or run out of items. It makes no assumption about order, so it works on any list.

def linear_search(items, target):
    for index in range(len(items)):   # index goes 0, 1, 2, ...
        if items[index] == target:
            return index              # found it; report the position
    return -1                         # looked at everything; not present

nums = [4, 8, 15, 16, 23, 42]
print(linear_search(nums, 23))   # -> 4
print(linear_search(nums, 9))    # -> -1

range(len(items)) produces the index numbers 0 up to one less than the length. -1 is a common signal for “not found” because it is never a valid index into the front of a list.

Complexity. In the worst case the target is the last item, or missing entirely, so we touch all n items: that is O(n) time. We use no extra storage that grows with the list, so it is O(1) space (constant). Linear search is the best you can do when the list is unsorted, because any item could be the target and you cannot rule any out without looking.

Binary search: using order to skip

If the list is sorted, we can do dramatically better. The idea is to always look at the middle item first. Because the list is ordered, that one comparison tells us which half the target must be in, and we throw the other half away. We repeat on the surviving half, halving the search each time.

Starting from six items, one comparison cuts the region to three, then to one, then to empty — and that steady halving is what makes the search fast:

flowchart TD
    A["Search region: 6 items<br/>low..high"] --> B["Look at mid, discard half"]
    B --> C["Region: 3 items"]
    C --> D["Look at mid, discard half"]
    D --> E["Region: 1 item"]
    E --> F["Look at mid, discard half"]
    F --> G["Region: 0 items -> stop"]

We track the region still worth searching with two index markers:

• low — the first index that could still hold the target.
• high — the last index that could still hold the target.
• mid — the middle index between them, computed each round.

At the start low is 0 and high is the last index. Each round we compute mid, compare arr[mid] to the target, and then move either low or high inward to discard the half that cannot contain the target.

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:                 # while the region is non-empty
        mid = (low + high) // 2        # // is integer division: drops any fraction
        if arr[mid] == target:
            return mid                 # exact hit
        elif arr[mid] < target:
            low = mid + 1              # target is in the right half
        else:
            high = mid - 1             # target is in the left half
    return -1                          # region emptied; not present

nums = [4, 8, 15, 16, 23, 42]
print(binary_search(nums, 23))   # -> 4
print(binary_search(nums, 10))   # -> -1

// is integer division: 7 // 2 is 3, not 3.5. It throws away the fractional part, which is exactly what we want for an index (indexes must be whole numbers).

Step-by-step trace

Now walk the code on a real target. We search for 23 in the sorted list below, with the indexes written above each value so the markers are easy to follow.

index:   0   1   2   3   4   5
value:   4   8  15  16  23  42

Each row shows the full state at the start of a round: the current low, high, the mid we compute, the value sitting at arr[mid], and the decision that follows.

Two comparisons on a six-item list. Now trace a missing target, 10, to see how the loop ends without a match:

When low passes high the region has no items left, the while condition low <= high becomes false, and the function returns -1.

Complexity. Each round discards half the remaining items, so the number of rounds is how many times n can be halved: that is O(log n) time. For a list of a million items that is about 20 comparisons instead of a million. Space is O(1): we only keep the three integer markers, no matter how big the list is.

The one-line derivation: start with n candidates, after one comparison at most n/2 remain, then n/4, then n/8, and so on until one is left. The count of halvings from n down to 1 is log2(n), which is the number of comparisons.

Why sorted matters

Binary search only works because the list is sorted. The middle comparison lets us discard a whole half precisely because everything to the left of a value is smaller and everything to the right is larger. On an unsorted list that guarantee is gone, one comparison tells you nothing about the other items, and you are back to linear search.

If you need to search a list many times, it can be worth sorting it once (sorting itself costs O(n log n)) so every later search is O(log n). If you search only once, plain linear search is simpler and avoids the sort.

Common pitfalls

• Off-by-one on high. high must start at len(arr) - 1, the last valid index, not len(arr). Using len(arr) would let mid point one past the end and cause an out-of-range error.
• Wrong loop condition. The condition must be low <= high, not low < high. With <, a region that has shrunk to a single item (where low == high) is skipped, and you can miss a target that sits exactly there.
• Infinite loop from not moving the markers. After comparing, you must move low to mid + 1 or high to mid - 1, using the +1/-1. If you instead wrote low = mid or high = mid, then in a two-item region mid can keep landing on the same index, the region never shrinks, and the loop runs forever. The +1 and -1 guarantee progress every round.
• Searching an unsorted list. Binary search on an unsorted list returns wrong answers silently. It does not error; it just trusts an order that is not there.
• Confusing “not found.” -1 is a sentinel value, not an index. Always check for it before using the result to index back into the list.

Python’s bisect module

Writing binary search by hand is a good exercise, but Python ships a tested implementation in the standard library called bisect (a module is a bundle of ready-made functions you import by name). It works on a sorted list and is built around finding the correct insertion point for a value.

import bisect

nums = [4, 8, 15, 16, 23, 42]

# bisect_left returns the index where target would be inserted to keep order.
pos = bisect.bisect_left(nums, 23)
print(pos)                       # -> 4

# Turn that into a membership test:
def contains(sorted_list, target):
    i = bisect.bisect_left(sorted_list, target)
    return i < len(sorted_list) and sorted_list[i] == target

print(contains(nums, 23))        # -> True
print(contains(nums, 10))        # -> False

bisect_left(nums, 23) reports the leftmost spot where 23 belongs, which for a present value is exactly its index. To confirm the value is actually there and not merely where it would go, we check that the index is in range and that the item at that index equals the target. bisect also has insort, which inserts a value into a sorted list while keeping it sorted:

import bisect

nums = [4, 8, 15, 16, 23, 42]
bisect.insort(nums, 20)
print(nums)                      # -> [4, 8, 15, 16, 20, 23, 42]

The lookup inside bisect is O(log n), the same as hand-written binary search. Note that insort still has to shift later items over to make room, so the insertion itself is O(n); only the position-finding is logarithmic.

Big-O summary

Practice

1. Write your own binary_search(arr, target) from scratch without looking at the version above. Test it on an empty list [], a single-item list [5], and a list where the target is the very first and very last element. Confirm it returns -1 for a value that is not present.

2. Modify binary search to return the index of the first occurrence when the sorted list contains duplicates, for example finding the first 7 in [3, 7, 7, 7, 9]. (Hint: when you find a match, do not stop; keep searching the left half.)

3. Given a sorted list and a target that may be missing, use bisect to find the value in the list that is closest to the target. Try it on [10, 20, 30, 40] with a target of 26 and check that you get 30.