Binary Search

What it is

Binary search finds a target in a sorted search space by repeatedly comparing the target to the middle element and discarding the half that can't contain it. Each comparison halves the remaining space, giving O(log n) time.

The core loop

low, high = 0, n - 1
while low <= high:
    mid = low + (high - low) // 2
    if arr[mid] == target: return mid
    elif arr[mid] < target: low = mid + 1
    else: high = mid - 1
return -1  # not found

Use low + (high - low) / 2 rather than (low + high) / 2 to avoid integer overflow when both bounds are large.

Complexity

• Time: O(log n)
• Space: O(1) iterative, O(log n) recursive (call stack)

Variants beyond "find the exact value"

• First/last occurrence with duplicates — on a match, keep narrowing instead of returning immediately.
• Rotated sorted array — at least one half relative to mid is always still sorted; determine which, then decide where the target could be.
• Binary search on the answer — search over a range of possible answers instead of array indices, using a monotonic feasibility check (e.g., "can we ship all packages within D days at capacity C?").
• Peak finding — compare arr[mid] to its neighbor to decide which direction still has a peak.

Why it doesn't work on a linked list

Binary search's speed depends on O(1) access to the middle element. A linked list only supports sequential access, so finding "mid" costs O(n) — doing that at every step erases the entire advantage.