Algorithms & Coding Interviews · Arrays, Strings & Linear Structures

Binary Search

Binary search finds a boundary among n candidates in O(log n), not just an element in a sorted array. Learn one bug-resistant template for exact matches, lower/upper bounds and search-on-the-answer, handle rotated arrays, and watch three LeetCode problems animated.

🧮 Algorithms & Coding Interviews● Intermediate⏱ 11 min read▶ 3 interactive🛠️ 4 exercises

🎯 What you'll learn

Exact match, boundary and search-on-the-answer flavours
One half-open template and its invariant
Rotated arrays and the partition idea
Six LeetCode problems up to Median of Two Sorted Arrays

📚 Before you start

Part 1The Pattern

Binary search halves the search space on every step, so it finds an answer among n candidates in O(log n): 30 steps for a billion items. It applies far beyond "find x in a sorted array": any time candidates can be split into a "no" part followed by a "yes" part (a monotonic predicate), you can binary search for the boundary. That includes searching for a numeric answer such as a speed, a capacity or a time.

Each step discards half of the remaining range

1Three Flavours

Flavour	Question	Example
Exact match	Is x present, and where?	Binary Search (704)
Boundary (lower/upper bound)	First index where `a[i] ≥ x` (or `> x`)	insert position, first/last occurrence, count of x
Search on the answer	Smallest value v such that `feasible(v)` is true	Koko Eating Bananas, ship packages, split array

2One Template to Rule Them All

Most bugs come from mixing up <= / < and mid / mid ± 1. Use one half-open template for everything and reason only about the predicate:

typescript

function lowerBound(nums: number[], target: number): number {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (nums[mid] < target) lo = mid + 1; else hi = mid;
  }
  return lo;
}

function minFeasible(lo: number, hi: number, feasible: (x: number) => boolean): number {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (feasible(mid)) hi = mid; else lo = mid + 1;
  }
  return lo;
}

python

def lower_bound(nums, target):
    """First index i with nums[i] >= target (len(nums) if none)."""
    lo, hi = 0, len(nums)                 # search space [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1                    # answer is right of mid
        else:
            hi = mid                        # mid could be the answer
    return lo

def min_feasible(lo, hi, feasible):
    """Smallest x in [lo, hi] with feasible(x) True; feasible must be monotonic (F..F T..T)."""
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Invariant: the answer is always inside [lo, hi) (or [lo, hi] in min_feasible). Each iteration shrinks the range by at least one, so the loop terminates, and when lo == hi that's the answer.

upper_bound(x) (first index with a[i] > x) is the same code with <= in the comparison.
count of x = upper_bound(x) − lower_bound(x).
Python has these built in: bisect.bisect_left and bisect.bisect_right. C# has Array.BinarySearch (returns the bitwise complement of the insertion point when not found).

3Search on the Answer

When asked for "the minimum X such that something is possible":

Identify the range of candidate answers [lo, hi] (e.g. speed 1 to max pile).
Write feasible(x), usually a greedy O(n) check.
Confirm monotonicity: if x works, every larger x works too.
Binary search the boundary: total O(n log range).

4Rotated and Partially Sorted Arrays

In a rotated sorted array, one half around mid is always sorted. Check which half is sorted (nums[lo] <= nums[mid]), test whether the target lies inside that sorted half, and discard the other. The minimum of a rotated array is found by comparing nums[mid] with nums[hi].

Under the HoodOverflow and Termination▾

mid = (lo + hi) / 2 can overflow 32-bit integers in C#/Java when lo + hi > 2³¹ − 1; use lo + (hi − lo) / 2. In JavaScript, (lo + hi) >>> 1 is a safe unsigned shift for array indices. Python integers don't overflow. Termination: with lo < hi, mid is always < hi, so hi = mid strictly shrinks the range and lo = mid + 1 does too. If you write lo = mid instead, the loop can get stuck when hi = lo + 1 (then you'd need mid = (lo + hi + 1) / 2).

⚠️ Common Pitfalls

Mixing templates (<= with hi = mid) → infinite loops or skipped answers.
Non-monotonic predicate: binary search silently returns garbage.
Integer overflow in (lo + hi) / 2 in typed languages.
Wrong answer range in search-on-answer (e.g. lower bound 0 when the answer must be ≥ 1).
Forgetting duplicates: with repeated values, decide whether you want the first or last occurrence.

📋 Quick Reference

text

lower_bound: lo,hi = 0,n; while lo<hi: mid; a[mid]<x → lo=mid+1 else hi=mid
upper_bound: same with a[mid] <= x
answer search: lo..hi range; feasible(mid) → hi=mid else lo=mid+1
rotated: one half is sorted; test target there
O(log n) · answer search O(n log range)

Part 2Interview Problems

Six problems across the three flavours: exact match, boundaries, rotated arrays, search on the answer, and the hard partition search.

1Binary Search (LeetCode 704)

🟢 Easy. Return the index of target in the sorted array nums, or −1.

text

nums = [-1,0,3,5,9,12], target = 9 → 4

Approach. Lower bound, then check that the element there equals the target.

Complexity. O(log n) time, O(1) space.

typescript

function search(nums: number[], target: number): number {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (nums[mid] < target) lo = mid + 1; else hi = mid;
  }
  return lo < nums.length && nums[lo] === target ? lo : -1;
}

python

def search(nums, target):
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo if lo < len(nums) and nums[lo] == target else -1

2Find First and Last Position of Element (LeetCode 34)

🟠 Medium. Return [first, last] positions of target in sorted nums, or [-1, -1], in O(log n).

text

nums = [5,7,7,8,8,10], target = 8 → [3,4]

Approach. first = lower_bound(target), last = lower_bound(target + 1) − 1 (or upper_bound − 1). If first is out of range or doesn't hold the target, return [-1, -1].

Complexity. O(log n) time.

typescript

function lowerBound(nums: number[], x: number): number {
  let lo = 0, hi = nums.length;
  while (lo < hi) { const mid = (lo + hi) >>> 1; if (nums[mid] < x) lo = mid + 1; else hi = mid; }
  return lo;
}

function searchRange(nums: number[], target: number): number[] {
  const first = lowerBound(nums, target);
  if (first === nums.length || nums[first] !== target) return [-1, -1];
  return [first, lowerBound(nums, target + 1) - 1];
}

python

from bisect import bisect_left

def search_range(nums, target):
    first = bisect_left(nums, target)
    if first == len(nums) or nums[first] != target:
        return [-1, -1]
    return [first, bisect_left(nums, target + 1) - 1]

3Search in Rotated Sorted Array (LeetCode 33)

🟠 Medium. A sorted array of distinct values was rotated at an unknown pivot. Return the index of target or −1 in O(log n).

text

nums = [4,5,6,7,0,1,2], target = 0 → 4

Approach. At every step one half of [lo, hi] is sorted. If nums[lo] <= nums[mid], the left half is sorted: go left if nums[lo] <= target < nums[mid], otherwise right. Else the right half is sorted: go right if nums[mid] < target <= nums[hi].

Complexity. O(log n) time, O(1) space.

typescript

function searchRotated(nums: number[], target: number): number {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >>> 1;
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) {
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1;
    }
  }
  return -1;
}

python

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:                    # left half sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                        # right half sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

4Find Minimum in Rotated Sorted Array (LeetCode 153)

🟠 Medium. Return the minimum of a rotated sorted array of distinct values in O(log n).

text

nums = [3,4,5,1,2] → 1

Approach. Compare nums[mid] with nums[hi]: if nums[mid] > nums[hi], the drop (and the minimum) is to the right of mid; otherwise the minimum is at mid or to its left.

Complexity. O(log n) time.

typescript

function findMin(nums: number[]): number {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (nums[mid] > nums[hi]) lo = mid + 1; else hi = mid;
  }
  return nums[lo];
}

python

def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

5Koko Eating Bananas (LeetCode 875)

🟠 Medium. Koko eats at speed k bananas/hour, one pile per hour at most (leftover hours are wasted). Return the minimum k that finishes all piles within h hours.

text

piles = [3,6,7,11], h = 8 → 4

Approach. Search on the answer. Speeds range from 1 to max(piles). hours(k) = Σ ceil(pile / k) decreases as k grows (monotonic), so binary search the smallest k with hours(k) ≤ h.

Complexity. O(n log max(piles)) time, O(1) space.

typescript

function minEatingSpeed(piles: number[], h: number): number {
  const hours = (k: number) => piles.reduce((t, p) => t + Math.ceil(p / k), 0);
  let lo = 1, hi = Math.max(...piles);
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (hours(mid) <= h) hi = mid; else lo = mid + 1;
  }
  return lo;
}

python

def min_eating_speed(piles, h):
    def hours(k):
        return sum((p + k - 1) // k for p in piles)   # ceil division
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours(mid) <= h:
            hi = mid
        else:
            lo = mid + 1
    return lo

6Median of Two Sorted Arrays (LeetCode 4)

🔴 Hard. Return the median of two sorted arrays in O(log(min(m, n))).

text

a = [1,2], b = [3,4] → 2.5

Approach. Binary search a partition of the shorter array A: take i elements from A and j = half − i from B so the left side holds half of all elements. The partition is correct when A[i−1] ≤ B[j] and B[j−1] ≤ A[i]; if A[i−1] > B[j], take fewer from A (move left), else more. The median comes from the max of the left side and the min of the right side.

Complexity. O(log min(m, n)) time, O(1) space.

typescript

function findMedianSortedArrays(a: number[], b: number[]): number {
  if (a.length > b.length) [a, b] = [b, a];
  const m = a.length, n = b.length, half = (m + n + 1) >> 1;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = (lo + hi) >> 1, j = half - i;
    const aL = i > 0 ? a[i - 1] : -Infinity, aR = i < m ? a[i] : Infinity;
    const bL = j > 0 ? b[j - 1] : -Infinity, bR = j < n ? b[j] : Infinity;
    if (aL <= bR && bL <= aR) {
      return (m + n) % 2 ? Math.max(aL, bL) : (Math.max(aL, bL) + Math.min(aR, bR)) / 2;
    }
    if (aL > bR) hi = i - 1; else lo = i + 1;
  }
  return 0;
}

python

def find_median_sorted_arrays(a, b):
    if len(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    half = (m + n + 1) // 2
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2
        j = half - i
        a_left = a[i - 1] if i > 0 else float("-inf")
        a_right = a[i] if i < m else float("inf")
        b_left = b[j - 1] if j > 0 else float("-inf")
        b_right = b[j] if j < n else float("inf")
        if a_left <= b_right and b_left <= a_right:
            if (m + n) % 2:
                return float(max(a_left, b_left))
            return (max(a_left, b_left) + min(a_right, b_right)) / 2
        if a_left > b_right:
            hi = i - 1
        else:
            lo = i + 1
    return 0.0

🧠 Key takeaways

Binary search needs a monotonic predicate (no…no yes…yes), not necessarily a sorted array.
Use one template: while lo < hi, hi = mid or lo = mid + 1; reason about the invariant.
Search on the answer: range of candidates + greedy feasibility check → O(n log range).
Rotated arrays: one half is sorted; avoid overflow with lo + (hi − lo) / 2.

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

algo_binary_search_exercise_1.py

TS PY

algo_binary_search_exercise_2.py

TS PY

✅ Check yourself

Answer the questions — feedback is instant.

1. Koko Eating Bananas binary searches over…

Search on the answer.

2. lower_bound returns…

Insertion point.

3. Why write mid = lo + (hi − lo) / 2 in C#?

Large indices overflow.

4. In a rotated sorted array, what's always true around mid?

Exploit the sorted half.

Source: algo_binary_search_theory_1.md, algo_binary_search_theory_2.md · generated by tools/build_lessons.py