Binary search

Find a needle in a sorted haystack by repeatedly cutting the search space in half.

The idea

If you're looking for a specific word in a dictionary, you don't read page by page from the beginning. You open it to the middle. If your word comes alphabetically before the middle page, you know you can completely ignore the entire second half of the book.

Binary search uses this exact logic on sorted arrays. By checking the middle element (mid), you instantly eliminate half of the remaining possibilities. This transforms a slow O(n) search into a blazing fast O(log n) search.

Enter a target and click Start Search.

How it works

We maintain an active search window [lo, hi]. We calculate mid, compare it to the target, and then aggressively squeeze the boundaries inward.

def binary_search(nums, target):
    lo = 0
    hi = len(nums) - 1
    
    while lo <= hi:
        # (lo + hi) // 2 can overflow in some languages (e.g. Java/C++).
        # lo + (hi - lo) // 2 is safer and mathematically identical.
        mid = lo + (hi - lo) // 2
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            # Target is strictly greater, so mid is too small.
            # We can safely eliminate everything up to and including mid.
            lo = mid + 1
        else:
            # Target is strictly smaller, so mid is too big.
            hi = mid - 1
            
    return -1 # Not found

Cost

Time Complexity O(log N)
Space Complexity O(1)

Because we cut the remaining possibilities in half every step, an array of 1,000,000 items takes at most 20 comparisons. (log&sub2;(1,000,000) ≈ 20).

Watch out for