Offensive Security Researcher & Quantum Cryptography Analyst

Develop a Function to Implement Binary Search: Complete Python Algorithm and Implementation Guide

Abdul Wahab Junaid
Develop a function to implement Binary Search

Develop a function to implement Binary Search

I remember the exact moment binary search clicked for me — I was searching through a sorted list of a few million records using a linear scan, and it was painfully slow. Someone pointed out I could exploit the fact that the data was sorted, and rewriting it as a binary search took the search time from something noticeable to essentially instantaneous. That contrast between O(n) and O(log n) stopped being an abstract complexity notation and became something I could feel in real runtime. Here’s the complete guide to implementing binary search properly in Python.

The Core Idea

Binary search works on sorted data by repeatedly halving the search space: check the middle element, and based on whether the target is smaller or larger, discard half the remaining elements entirely. This only works because the data is sorted — on unsorted data, there’s no meaningful way to decide which half to discard.

Iterative Implementation

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
        else:
            high = mid - 1

    return -1  # not found

numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(binary_search(numbers, 13))  # 6
print(binary_search(numbers, 4))   # -1

Let me walk through exactly what happens searching for 13:

Each step eliminates roughly half of the remaining candidates, which is exactly why this algorithm is so much faster than scanning element by element.

Why (low + high) // 2 Can Be Subtly Wrong (And the Fix)

In languages with fixed-size integers (like Java or C), computing (low + high) // 2 can overflow if low and high are both very large, since their sum might exceed the maximum representable integer before the division happens. This is a famous, historically real bug — it existed in published binary search implementations for years before being widely recognized.

mid = low + (high - low) // 2

This alternative formula avoids ever computing a sum that could overflow, since it only ever adds a (necessarily smaller) difference to low. In Python specifically, this isn’t a practical concern, because Python’s integers have arbitrary precision and never overflow — but I still use this safer formula out of habit, since it’s a good practice that transfers directly to other languages and demonstrates awareness of a genuinely famous algorithmic pitfall.

Recursive Implementation

def binary_search_recursive(arr, target, low=0, high=None):
    if high is None:
        high = len(arr) - 1

    if low > high:
        return -1

    mid = low + (high - low) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        return binary_search_recursive(arr, target, low, mid - 1)

print(binary_search_recursive(numbers, 13))  # 6
print(binary_search_recursive(numbers, 100)) # -1

The recursive version is conceptually elegant — each call handles exactly one comparison and delegates the rest to a smaller sub-problem — but it comes with a caveat in Python specifically: Python has no tail-call optimization, so deep recursion (searching an extremely large array) consumes real stack frames and can hit Python’s recursion limit (sys.getrecursionlimit(), typically 1000 by default) for sufficiently large inputs. For genuinely huge datasets, I generally prefer the iterative version to avoid this risk entirely.

Finding the Insertion Point (Not Just Exact Matches)

A useful variant of binary search finds where a target should be inserted to keep the array sorted, even if the exact value isn’t present — this is exactly what Python’s own bisect module provides.

def binary_search_insertion_point(arr, target):
    low = 0
    high = len(arr)

    while low < high:
        mid = low + (high - low) // 2
        if arr[mid] < target:
            low = mid + 1
        else:
            high = mid

    return low

print(binary_search_insertion_point([1, 3, 5, 7, 9], 6))  # 3 — would go between 5 and 7

Using Python’s Built-In bisect Module

I want to be upfront: for real production code, I almost never hand-roll binary search from scratch — Python’s standard library already provides a well-tested, optimized implementation via the bisect module.

import bisect

numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

index = bisect.bisect_left(numbers, 13)
print(index)  # 6

# Check if the value actually exists at that position
def contains(arr, target):
    i = bisect.bisect_left(arr, target)
    return i < len(arr) and arr[i] == target

print(contains(numbers, 13))  # True
print(contains(numbers, 14))  # False

bisect.bisect_left() and bisect.bisect_right() differ in how they handle duplicate values — bisect_left finds the leftmost position where the target could be inserted, bisect_right finds the rightmost. This distinction matters when your array contains repeated values and you need to find the boundary of a range of duplicates.

import bisect

sorted_with_dupes = [1, 2, 2, 2, 3, 4]

print(bisect.bisect_left(sorted_with_dupes, 2))   # 1 — before the first 2
print(bisect.bisect_right(sorted_with_dupes, 2))  # 4 — after the last 2

Time and Space Complexity

Binary search runs in O(log n) time, because each comparison eliminates half of the remaining search space. Starting with n elements, after k comparisons, the remaining search space is n / 2^k — the search terminates once this shrinks to a single element, which happens after roughly log2(n) steps.

import math

n = 1_000_000
print(math.log2(n))  # approximately 19.9 — so at most ~20 comparisons needed

Compare this to linear search’s O(n) — for a million elements, linear search might need up to a million comparisons in the worst case, while binary search needs at most about 20. This difference becomes dramatic as data size grows, which is exactly why sorted data structures paired with binary search are so foundational to efficient computing.

Space complexity: the iterative version uses O(1) additional space (just a few variables). The recursive version uses O(log n) additional space due to the call stack, since each recursive call adds a stack frame, and there are O(log n) of them before the base case is reached.

Real-World Applications

Common Mistakes

Running binary search on unsorted data. This is the single most fundamental mistake — binary search’s correctness entirely depends on the data being sorted; running it on unsorted data produces meaningless, often incorrect results without any error being raised.

Off-by-one errors in the loop condition or bounds update. Using low < high instead of low <= high (or vice versa) inconsistently with how mid + 1 / mid - 1 are computed is a classic source of bugs — infinite loops or missed matches at the boundaries.

Forgetting to update low or high correctly, leading to infinite loops. For example, forgetting +1 in low = mid + 1 (using low = mid instead) can cause the loop to never terminate if mid equals low.

Using deep recursion on very large inputs without considering Python’s recursion limit, risking a RecursionError on inputs large enough to require more recursive calls than the limit allows.

Reinventing bisect unnecessarily. For most practical purposes, Python’s built-in bisect module is faster (implemented in C) and better tested than a hand-rolled version — reach for it in production code rather than rewriting the algorithm from scratch every time.

Debugging Tips

Performance Considerations

FAQs

Does binary search work on unsorted data? No — the algorithm’s correctness fundamentally depends on the data being sorted. Running it on unsorted data gives unreliable, often wrong results.

What’s the difference between bisect_left and bisect_right? bisect_left returns the leftmost valid insertion point for a target (before any existing equal elements), while bisect_right returns the rightmost (after any existing equal elements) — they only differ in behavior when duplicate values are present.

Is recursive or iterative binary search better in Python? Iterative is generally preferred in Python specifically, since it avoids consuming stack frames and isn’t subject to Python’s recursion limit, which can matter for very large inputs.

How does binary search compare to using a hash table (dictionary) for lookups? A dictionary lookup is O(1) average case, faster than binary search’s O(log n) — but dictionaries don’t maintain order or support range queries (like “find all values between X and Y”) the way a sorted array with binary search does. The right choice depends on what operations you actually need.

Summary

Binary search is one of the most fundamental and instructive algorithms in computer science — a simple halving strategy that turns an O(n) linear scan into an O(log n) search, provided the underlying data is sorted. Implementing it correctly means being careful about loop bounds, avoiding subtle off-by-one errors, and understanding the trade-off between the elegant recursive form and the stack-safe iterative form. For real production code, Python’s built-in bisect module already provides a fast, well-tested implementation — understanding the algorithm from scratch, though, is what makes reasoning about its performance and correctly applying variants (like insertion-point search) genuinely intuitive.

References

Exit mobile version