Binary Search

Searching

Complexity: Time O(log n), Space O(1)

Uses

Fast lookup in sorted arrays or lists
Lower/upper bound searches in sorted data
Finding the first/last occurrence of a condition

Considerations & trade-offs

Requires sorted input to be correct
Random access is needed for O(log n); linked lists degrade to O(n)
Off-by-one errors are common; test boundaries

1) Header + quick facts

Aliases: Half-interval search, log search.

Primary idea: Compare to the middle, keep the half that can still contain the answer.

When to use: Sorted input with fast random access.

Related topics: Algorithms index, Arrays

2) Problem it solves

Inputs: Sorted list or array and a target value.

Output: Index of the target, or -1 if not found.

What is non-trivial: Avoid off-by-one errors while shrinking the search window.

Typical signals: Sorted data + need fast membership or first occurrence.

3) Core intuition

Invariant: If the target exists, it is always within [left, right].

Progress: Each step halves the search range.

Mental image: Shrink a window around the target with each comparison.

4) Complexity + tradeoffs

Time	Best O(1), Average O(log n), Worst O(log n)
Space	Auxiliary O(1), Total O(1)
Behavior	In-place, does not mutate input
Sensitivity	Requires random access and sorted input

5) Pseudocode

binary_search(items, target):
  left = 0
  right = length(items) - 1
  while left <= right:
    mid = floor((left + right) / 2)
    if items[mid] == target:
      return mid
    if items[mid] < target:
      left = mid + 1
    else:
      right = mid - 1
  return -1

6) Reference implementation (Python)

def binary_search(items, target):
    # Invariant: if target exists, it is within [left, right].
    left = 0
    right = len(items) - 1

    while left <= right:
        mid = (left + right) // 2
        value = items[mid]

        if value == target:
            return mid
        if value < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

7) Tests

def test_binary_search_found():
    items = [1, 4, 6, 9, 11, 15, 18]
    assert binary_search(items, 9) == 3


def test_binary_search_missing():
    items = [2, 3, 5, 7, 11]
    assert binary_search(items, 8) == -1


def test_binary_search_edges():
    items = [10, 20, 30]
    assert binary_search(items, 10) == 0
    assert binary_search(items, 30) == 2

8) Common pitfalls

Using < instead of <= for the loop condition
Not updating left/right correctly when mid is not a match
Running on unsorted data
Assuming it works on linked lists with the same complexity

9) Variants + extensions

Lower/upper bound to find first or last occurrence
Binary search on answer (monotonic predicate)
Recursive variant for teaching clarity

10) Use cases

Systems: lookup in sorted ID tables
Data: find cut points or thresholds
UI: range selection or pagination windows

11) When not to use it

Input is unsorted or expensive to sort
Only sequential access is available
Data is tiny and linear scan is simpler

12) Associated concepts

Prerequisites: Arrays, invariants

Pairs well with: Two pointers, lower/upper bounds

Next to learn: Binary search on answer, partition schemes

13) Implementation notes

Branch prediction can affect tight loops; keep it simple
Return indices, not slices, to avoid extra allocations
Instrument comparisons if used in production search APIs