PATTERN 5 OF 22

Binary Search

Find elements or boundaries in sorted data in O(log n) time by repeatedly halving the search space. Also applies to "binary search on the answer space" for optimization problems.

Time: O(log n)

Space: O(1)

Learn & Reference

Understanding the Pattern

Binary Search Pattern

Binary search is one of the most fundamental algorithms in computer science. At its core, it exploits sorted order (or a monotonic property) to eliminate half the search space in each step, achieving O(log n) time instead of O(n).

Core Concept

Given a sorted array, instead of scanning every element, pick the middle element and compare:

If it matches the target, you're done
If the target is smaller, search the left half
If the target is larger, search the right half

Each comparison eliminates half the remaining elements. For an array of 1,000,000 elements, you need at most 20 comparisons (log₂(1,000,000) ≈ 20).

The 3 Binary Search Archetypes

1. Standard Element Search (`lo <= hi`)

Find a specific target in a sorted array. Returns its index or -1 if not found.

Template:

lo, hi = 0, n - 1
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1
return -1

Key: lo <= hi ensures every element is checked. Both lo and hi move past mid.

2. Boundary Finding / Bisect (`lo < hi`)

Find the leftmost or rightmost position satisfying a condition. Used for "first true" or "last true" in a boolean sequence.

Template (find leftmost true):

lo, hi = 0, n - 1
while lo < hi:
    mid = lo + (hi - lo) // 2
    if condition(mid):
        hi = mid          # mid could be the answer
    else:
        lo = mid + 1      # mid is not the answer
return lo

Key: lo < hi terminates when they converge. One pointer moves to mid, the other past it.

3. Binary Search on the Answer Space

Instead of searching an array, search over a range of possible answers. Used for optimization problems where you can check "is answer X feasible?"

Template:

lo, hi = min_possible, max_possible
while lo < hi:
    mid = lo + (hi - lo) // 2
    if is_feasible(mid):
        hi = mid          # try smaller answer
    else:
        lo = mid + 1      # need larger answer
return lo

Key: The feasibility function must be monotonic — once feasible at some value, it stays feasible for all larger (or smaller) values.

When Binary Search Fails

The data is not sorted and has no monotonic property
You need to find all occurrences, not just one boundary
The "feasibility" function is not monotonic (feasible → infeasible → feasible)
The search space cannot be halved by a single comparison

Common Mistakes

Integer overflow in mid calculation: mid = (lo + hi) / 2 overflows for large values. Always use mid = lo + (hi - lo) / 2
Wrong loop condition: Using lo < hi for standard search misses the last element. Using lo <= hi for boundary search causes infinite loops
Off-by-one in pointer updates: For lo <= hi, both pointers must move past mid (lo = mid + 1, hi = mid - 1). For lo < hi, exactly one pointer stays at mid
Infinite loop from wrong mid update: If hi = mid and lo = mid are both possible, the loop never terminates. One side must always move past mid
Comparing to wrong reference in rotated arrays: In rotated array problems, comparing nums[mid] to nums[lo] vs nums[hi] gives different results — choose carefully

When to Use

Sorted array or sorted input

Find target in O(log n) time

Find the first/last position of X

Find minimum/maximum value that satisfies a condition

Rotated sorted array problems

Minimize the maximum or maximize the minimum — binary search on answer space

A feasibility check that is monotonic (once true, stays true)

Keywords: sorted, search, find, minimum, maximum, rotated, O(log n)

Current brute force is O(n) linear scan on sorted data

Template

1# --- Standard Binary Search (find target) ---
2def binary_search(nums, target):
3    lo, hi = 0, len(nums) - 1
4    while lo <= hi:
5        mid = lo + (hi - lo) // 2
6        if nums[mid] == target:
7            return mid
8        elif nums[mid] < target:
9            lo = mid + 1
10        else:
11            hi = mid - 1
12    return -1  # not found
13
14# --- Boundary Search (find first position where condition is true) ---
15def find_boundary(nums):
16    lo, hi = 0, len(nums) - 1
17    while lo < hi:
18        mid = lo + (hi - lo) // 2
19        if condition(nums[mid]):
20            hi = mid        # mid might be the answer
21        else:
22            lo = mid + 1    # mid is not the answer
23    return lo
24
25# --- Binary Search on Answer Space ---
26def min_answer(lo, hi):
27    while lo < hi:
28        mid = lo + (hi - lo) // 2
29        if is_feasible(mid):
30            hi = mid
31        else:
32            lo = mid + 1
33    return lo

{ }

Syntax Reference

1# --- bisect module (binary search utilities) ---
2import bisect
3
4# bisect_left: index where target would be inserted (leftmost position)
5i = bisect.bisect_left(arr, target)        # arr must be sorted
6# bisect_right: index after the last occurrence of target
7j = bisect.bisect_right(arr, target)
8
9# insort: insert while maintaining sorted order
10bisect.insort_left(arr, val)               # O(n) due to shifting
11bisect.insort_right(arr, val)
12
13# Check if target exists
14def binary_search(arr, target):
15    i = bisect.bisect_left(arr, target)
16    return i < len(arr) and arr[i] == target
17
18# Count occurrences of target
19count = bisect.bisect_right(arr, target) - bisect.bisect_left(arr, target)
20
21# --- Manual binary search ---
22lo, hi = 0, len(arr) - 1
23while lo <= hi:
24    mid = lo + (hi - lo) // 2
25    if arr[mid] == target:
26        return mid
27    elif arr[mid] < target:
28        lo = mid + 1
29    else:
30        hi = mid - 1

📋

Common Recipes

1# --- Standard Binary Search ---
2def binary_search(nums, target):
3    lo, hi = 0, len(nums) - 1
4    while lo <= hi:
5        mid = lo + (hi - lo) // 2
6        if nums[mid] == target:
7            return mid
8        elif nums[mid] < target:
9            lo = mid + 1
10        else:
11            hi = mid - 1
12    return -1
13
14# --- Find First/Last Position (bisect) ---
15import bisect
16def search_range(nums, target):
17    left = bisect.bisect_left(nums, target)
18    if left >= len(nums) or nums[left] != target:
19        return [-1, -1]
20    right = bisect.bisect_right(nums, target) - 1
21    return [left, right]
22
23# --- Binary Search on Answer Space ---
24def min_feasible(lo, hi, is_feasible):
25    """Find minimum value in [lo, hi] where is_feasible(x) is True."""
26    while lo < hi:
27        mid = lo + (hi - lo) // 2
28        if is_feasible(mid):
29            hi = mid
30        else:
31            lo = mid + 1
32    return lo
33
34# --- Search in Rotated Sorted Array ---
35def search_rotated(nums, target):
36    lo, hi = 0, len(nums) - 1
37    while lo <= hi:
38        mid = lo + (hi - lo) // 2
39        if nums[mid] == target:
40            return mid
41        if nums[lo] <= nums[mid]:  # left half sorted
42            if nums[lo] <= target < nums[mid]:
43                hi = mid - 1
44            else:
45                lo = mid + 1
46        else:                       # right half sorted
47            if nums[mid] < target <= nums[hi]:
48                lo = mid + 1
49            else:
50                hi = mid - 1
51    return -1

O(n)

Complexity

Operation	Time	Space
Standard search (find target)	O(log n)	O(1)
Bisect left / right (find boundary)	O(log n)	O(1)
Search in rotated sorted array	O(log n)	O(1)
Binary search on answer space	O(log(range) × check)	O(1)
Median of two sorted arrays	O(log(min(m, n)))	O(1)

Watch Out

✗The data is **not sorted** and has no monotonic property
✗You need to find **all** occurrences, not just one boundary
✗The "feasibility" function is not monotonic (feasible → infeasible → feasible)
✗The search space cannot be halved by a single comparison
✗Integer overflow in mid calculation: `mid = (lo + hi) / 2` overflows for large values. Always use `mid = lo + (hi - lo) / 2`
✗Wrong loop condition: Using `lo < hi` for standard search misses the last element. Using `lo <= hi` for boundary search causes infinite loops
✗Off-by-one in pointer updates: For `lo <= hi`, both pointers must move past mid (`lo = mid + 1`, `hi = mid - 1`). For `lo < hi`, exactly one pointer stays at mid
✗Infinite loop from wrong mid update: If `hi = mid` and `lo = mid` are both possible, the loop never terminates. One side must always move past mid
✗Comparing to wrong reference in rotated arrays: In rotated array problems, comparing `nums[mid]` to `nums[lo]` vs `nums[hi]` gives different results — choose carefully

PRACTICE PROBLEMS

Prefix Sums

Stacks & Monotonic Stacks