AW Dev Rethought

✂️ Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away - Antoine de Saint-Exupéry

🔍 Python Algorithm Lab — Binary Search 🐍


Description:

Binary search is not just “check the middle.” Its central idea is proving that an entire section cannot contain the target, then removing that section from consideration.

That proof depends on the input already being sorted.


Why discarding a half is safe

Consider this ascending sorted list:

values = [3, 7, 11, 18, 24, 31, 42, 56, 63]

To find 31, start with the middle value, 24. Every value before it is at most 24, so none can equal 31. Discard 24 and everything before it.

The middle of the remaining interval is 42. Every value after it is at least 42, so discard 42 and everything after it. The remaining candidate is 31.

Probe low mid high Middle value Action
1 0 4 8 24 Set low to 5
2 5 6 8 42 Set high to 5
3 5 5 5 31 Return index 5

Indices are zero-based. The result is the location 5, not the value 31.


Use one boundary convention consistently

This version uses an inclusive candidate interval [low, high]:

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

The invariant is: if a match exists, at least one matching value remains inside the candidate interval. The input must be ascending sorted, with consistent comparisons, and must not change during the search.

The +1 and -1 exclude the middle element we have already checked. They ensure that every unsuccessful probe makes the interval smaller. Mixing inclusive and exclusive boundary rules is a common source of errors.


A missing target leaves an empty interval

Searching for 30 visits the same middle values 24, 42, 31. At the last probe, 31 is too large, so high becomes 4 while low remains 5. The loop stops and returns None.

assert binary_search(values, 31) == 5
assert binary_search(values, 30) is None
assert binary_search([], 31) is None

Check results using is not None, rather than truthiness: index 0 is a successful result too.

index = binary_search(values, 3)
if index is not None:
    print(values[index])  # 3

Complexity without misleading speed claims

Each unsuccessful probe keeps at most half of the current candidates. On a Python list with constant-time indexing and comparisons, the iterative search takes O(log n) worst-case time and O(1) auxiliary space.

These bounds describe the search itself. Sorting first has its own cost. Checking sortedness on every call would also add linear work, so this implementation treats sorted input as a precondition. It moves indices rather than copying list slices.

The notebook's optional trace stores O(log n) records for teaching. That extra storage is separate from the untraced algorithm. Probe counts are not a wall-clock benchmark.


Duplicates and the standard library

The implementation returns any matching index. It does not guarantee the first duplicate.

Python's bisect_left instead returns the leftmost insertion position. To use it for exact lookup, check that the position is within the list and actually contains the target. See the official bisect documentation.

from bisect import bisect_left

items = [2, 4, 4, 4, 9]
position = bisect_left(items, 4)
index = position if position < len(items) and items[position] == 4 else None
assert index == 1

Run and verify

Open Binary_Search.ipynb in Jupyter. It uses only the standard library and contains the full implementation, actual found/missing traces, and 1,260 exhaustive small cases. Checks cover empty and singleton sequences, endpoints, absent targets, duplicates, valid bounds, and shrinking intervals.

A supplementary binary_search.py is included for standalone use.

Takeaway: sorted order justifies the discard; consistent boundaries and progress make the search correct.


Link copied!

Comments

Add Your Comment

Comment Added!