# Binary Search (Beyond the Sorted Array) > Master the binary search algorithm once and for all — the invariant that kills off-by-one bugs, and the "search on the answer" trick that works on problems that don't look like binary search at all. Canonical: https://ironclad.academy/dsa/techniques/binary-search | Difficulty: medium | Topics: Binary Search, Searching, Techniques Asked at: Google, Amazon, Meta, Microsoft ## Key takeaways - The invariant is everything. In the closed-interval template: [lo, hi], loop while lo <= hi, always move boundaries to mid ± 1. The first-true template (while lo < hi) moves hi to mid by design — pick one, never mix them. - Finding first/last occurrence is the same loop — you just keep searching after a match instead of returning immediately. - Binary search on the answer works whenever you can define a monotonic predicate: "is X feasible?" flips from false to true exactly once. - Rotated sorted arrays with distinct elements are O(log n) because one half is always unambiguously sorted — check which half, then decide where to go. Duplicates degrade the worst case to O(n). - If a problem asks for a minimum value under a constraint and you can check feasibility fast, binary search on the answer is almost certainly the move. > **In one line:** Binary search halves your search space at each step — but the real skill is recognizing when your problem *is* a binary search in disguise, even when there's no array in sight. The classic framing: sorted array, find a value, O(log n). That version is straightforward. The bugs come from sloppy boundary handling, and the missed opportunities come from not seeing the deeper pattern. Two things to internalize: 1. **Nail the invariant.** A closed interval `[lo, hi]`, `while lo <= hi`, move to `mid ± 1`. That one template handles classic search, find-first, find-last, and rotated arrays without reinventing anything. 2. **Binary search on the answer.** If a problem asks "what is the minimum X such that Y is possible?" and Y is monotonic in X, you can binary search over X directly — no sorted array needed. This pattern shows up constantly on Google and Meta hard problems. Hunting for 7 in `[1, 3, 5, 7, 9, 11, 14, 18, 22]`: ```text lo=0 hi=8 mid=4 arr[4]=9 > 7 → hi=3 candidates: 9 → 4 lo=0 hi=3 mid=1 arr[1]=3 < 7 → lo=2 candidates: 4 → 2 lo=2 hi=3 mid=2 arr[2]=5 < 7 → lo=3 candidates: 2 → 1 lo=3 hi=3 mid=3 arr[3]=7 == 7 → found at index 3 ``` Each comparison kills half the remaining candidates — four steps take 9 elements down to 1. ## The bug you've definitely written Here's the code most people write from memory: ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo < hi: # bug 1 mid = (lo + hi) // 2 if arr[mid] == target: return mid elif arr[mid] < target: lo = mid + 1 else: hi = mid # bug 2 return -1 ``` There are two bugs, and they conspire. `while lo < hi` exits before checking the last candidate, so a single-element array returns -1 even when the element matches. Bug 2 is `hi = mid` instead of `hi = mid - 1`. On its own it doesn't hang this loop — when `lo` and `hi` are adjacent, `mid` computes to `lo`, `hi` drops to `lo`, and `lo < hi` goes false — but it means `mid` is never ruled out. Now watch what happens when you spot bug 1 and apply the obvious fix, changing the condition to `lo <= hi`: once `lo == hi`, `mid == lo == hi`, `hi = mid` changes nothing, and the loop runs forever. Patching one bug without the other trades a wrong answer for a hang. These aren't obscure edge cases. They will eat your contest submission or your onsite if you're not careful. ## The template you can trust Pick one formulation and commit to it. Here's the one that works: ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 # closed interval: both endpoints are valid candidates while lo <= hi: # loop until the interval is empty mid = lo + (hi - lo) // 2 # avoids integer overflow (matters in C/Java) if arr[mid] == target: return mid elif arr[mid] < target: lo = mid + 1 # mid is ruled out; search [mid+1, hi] else: hi = mid - 1 # mid is ruled out; search [lo, mid-1] return -1 # target not present ``` The invariant: **at every point in the loop, if the target exists, it's somewhere in `[lo, hi]`**. When we find `arr[mid] < target`, the target can't be at `mid` or anywhere left of it, so `lo = mid + 1` preserves the invariant. Same logic for the other branch. When `lo > hi`, the interval is empty — the target isn't there. The `mid = lo + (hi - lo) // 2` instead of `(lo + hi) // 2` matters in languages with fixed-size integers. In Python integers don't overflow so it's style, but write it the safe way anyway — the habit saves you in Java or C++. Trace it on `[1, 3, 5, 7, 9, 11, 14, 18, 22]` with a target that isn't there — 8: ```text lo=0 hi=8 mid=4 arr[4]=9 > 8 → hi=3 lo=0 hi=3 mid=1 arr[1]=3 < 8 → lo=2 lo=2 hi=3 mid=2 arr[2]=5 < 8 → lo=3 lo=3 hi=3 mid=3 arr[3]=7 < 8 → lo=4 lo=4 > hi=3 — interval empty, return -1 ``` The interval shrinks 9 → 4 → 2 → 1 → empty, and the miss falls out of the invariant with no special-casing. That's log base 2 of 9 ≈ 3.2, so 4 comparisons in the worst case. For 1 million elements, you need at most 20. ## Find first / find last: same loop, different boundary Sorted arrays with duplicates: `[1, 2, 4, 4, 4, 6, 7]`. You want the index of the first `4` (should be 2) or the last `4` (should be 4). The naive idea — find any occurrence, then walk left or right — degrades to O(n) on all-equal arrays. The binary search version keeps the same skeleton. When you hit a match, instead of returning, you record the candidate and keep narrowing: ```python def find_first(arr, target): lo, hi = 0, len(arr) - 1 result = -1 while lo <= hi: mid = lo + (hi - lo) // 2 if arr[mid] == target: result = mid # record it, but keep going left hi = mid - 1 elif arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return result def find_last(arr, target): lo, hi = 0, len(arr) - 1 result = -1 while lo <= hi: mid = lo + (hi - lo) // 2 if arr[mid] == target: result = mid # record it, but keep going right lo = mid + 1 elif arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return result ``` Both are O(log n). The match condition becomes "continue, but remember where you are" rather than "stop." This same idea — don't stop at the first match, keep pushing the boundary in one direction — reappears in every binary search variant. In production code, don't hand-roll any of this. Python's `bisect_left` is `find_first`'s boundary — it returns the insertion point, so check `arr[i] == target` afterward — and `bisect_right` gives you one past the last occurrence. C++ has `lower_bound`/`upper_bound`; Java has `Arrays.binarySearch` (which returns *some* matching index, not the first). Since Python 3.10, `bisect_left` also takes a `key=`, which covers most first-true searches over data you already hold in a list. Write the loop yourself in exactly two situations: interviews, and search-on-the-answer, where the predicate isn't membership in an array you can hand to a library. ## Rotated sorted array This one shows up constantly. Take a sorted array like `[1, 3, 5, 7, 9, 11, 14]` and rotate it at some pivot: `[7, 9, 11, 14, 1, 3, 5]`. The array isn't globally sorted anymore, but it has a key property: **one of the two halves (split at mid) is always sorted**. ```mermaid flowchart LR A["[7, 9, 11, 14, 1, 3, 5]"] --> B{"arr[mid]=14\narr[lo]=7\narr[hi]=5"} B -- "arr[lo] ≤ arr[mid]\n→ left half sorted" --> C["Target in [7,14]?\nSearch left\nElse search right"] B -- "arr[mid] < arr[lo]\n→ right half sorted" --> D["Target in [mid,hi]?\nSearch right\nElse search left"] style A fill:#7c5cff,color:#0a0a0f style C fill:#22d3ee,color:#0a0a0f style D fill:#00ff9d,color:#0a0a0f ``` The insight: if `arr[lo] <= arr[mid]`, the left half `[lo..mid]` is cleanly sorted. You can check in O(1) whether the target falls in that range — if yes, search there; if no, search the right half. Otherwise, the right half `[mid..hi]` is sorted, and you do the same check. ```python def search_rotated(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if arr[mid] == target: return mid if arr[lo] <= arr[mid]: # left half is sorted if arr[lo] <= target < arr[mid]: hi = mid - 1 # target is in the sorted left half else: lo = mid + 1 # target must be in the right half else: # right half is sorted if arr[mid] < target <= arr[hi]: lo = mid + 1 # target is in the sorted right half else: hi = mid - 1 # target must be in the left half return -1 ``` Still O(log n) — with one caveat: the half-is-sorted argument assumes **distinct elements**. With duplicates, say `[1, 1, 1, 1, 0, 1, 1]`, `arr[lo] <= arr[mid]` no longer proves the left half is sorted, because both boundaries can equal `arr[mid]`. The standard patch: when `arr[lo] == arr[mid] == arr[hi]`, you can't classify either half, so shrink with `lo += 1; hi -= 1` and continue. That preserves correctness, but an all-equal array with one different value hidden somewhere forces you to shrink one step at a time — worst case O(n), and no algorithm does better on that input. The half-is-sorted observation is the key — without it you can't safely discard anything. ## The real skill: binary search on the answer This is where binary search goes from "I know the algorithm" to "I can use it to demolish hard problems." The setup: you have a problem that asks for the **minimum (or maximum) value X** such that some condition holds. If that condition is **monotonic** — once it's true for some X, it's true for all larger X (or all smaller) — you can binary search over the range of possible X values. The pattern: ```python def solve(): lo, hi = lower_bound, upper_bound # range of possible answers while lo < hi: # find the first value that satisfies mid = lo + (hi - lo) // 2 if feasible(mid): # check if mid is a valid answer hi = mid # mid works, but maybe something smaller does too else: lo = mid + 1 # mid doesn't work, need something larger return lo # lo == hi: the smallest feasible value ``` Notice `while lo < hi` here — we want `lo == hi` at the end (both point to the answer), not an empty interval. And `hi = mid` (not `mid - 1`) because `mid` itself might be the answer. ### Worked example: Koko eats bananas Koko has `n` piles of bananas, `h` hours to eat them all. She eats at speed `k` bananas per hour (one pile at a time, and she waits if she finishes a pile early). What's the minimum `k`? The monotonic structure: if speed `k` works (she finishes in `<= h` hours), any speed `> k` also works. We want the smallest `k` that works. ```python def min_eating_speed(piles, h): import math def feasible(speed): # how many hours does this speed take? return sum(math.ceil(p / speed) for p in piles) <= h lo, hi = 1, max(piles) # speed 1 to max pile size (eating a pile per hour) while lo < hi: mid = lo + (hi - lo) // 2 if feasible(mid): hi = mid # mid works, look for something smaller else: lo = mid + 1 # mid is too slow return lo ``` The feasibility check is O(n). The binary search runs O(log(max(piles))) times. Total: O(n log m) where m is the max pile size. Without binary search on the answer, brute-forcing every possible speed from 1 to m would be O(n·m) — with piles of 10^9 bananas, that's not happening. ### What "monotonic" looks like in the wild The predicate `feasible(mid)` doesn't have to be obvious at first glance. Ask yourself: if I increase the candidate value by 1, does it become strictly easier or strictly harder to satisfy the constraint? If yes in one direction, you have a monotonic predicate. Some examples you'll see in interviews: | Problem | Candidate X | Predicate | | --- | --- | --- | | Ship packages in D days (LeetCode 1011) | Ship capacity | Can we ship all packages in D days at capacity X? | | Split array into k parts with min max-sum | Subarray max sum | Can we split into k parts where each part's sum ≤ X? | | Find peak element | — | Different structure; use lo/hi but on a derivative condition | | Kth smallest in sorted matrix | Matrix value | How many elements ≤ X? Is it ≥ k? | The template is the same every time. What changes is what `lo`, `hi`, and `feasible` mean. ## Complexity Binary search's power is exactly what it sounds like: | Variant | Time | Space | | --- | --- | --- | | Classic search (sorted array) | O(log n) | O(1) | | Find first / find last | O(log n) | O(1) | | Rotated sorted array | O(log n) distinct, O(n) with duplicates | O(1) | | Binary search on answer | O(log(range) × f(n)) | O(1) + whatever f(n) uses | The O(1) space is often undersold. Most O(log n) solutions you see use recursion — which brings O(log n) stack frames. The iterative version above is flat, using just `lo`, `hi`, and `mid`. ## Common mistakes **Forgetting that mid can equal lo.** With round-down division, `lo = 4` and `hi = 5` gives `mid = 4 = lo`. If you then set `lo = mid` in a "target is larger" branch, nothing changes — same `lo`, same `hi`, same `mid` next iteration — and you loop forever. The closed-interval template avoids this because it always steps past `mid`: `lo = mid + 1` or `hi = mid - 1`. **Using `while lo < hi` when you want to check the found element.** The `lo < hi` loop terminates with `lo == hi` — you still have to check `arr[lo]` after the loop. The `lo <= hi` template checks `mid` inside the loop every time, so you never need a post-loop check. **Binary searching on a non-monotonic predicate.** "Find the element closest to the median" is not monotonic in the way that lets you binary search directly. If your predicate can flip from false→true→false as X increases, binary search will give you garbage. Confirm monotonicity before reaching for the pattern. **Integer division in the wrong place.** `mid = (lo + hi) // 2` always rounds down. That's usually fine, but in the "search for last occurrence" or "find upper bound" variants, you sometimes want `mid = lo + (hi - lo + 1) // 2` (round up) to avoid the same infinite-loop issue where `mid == lo` when the interval has two elements and you set `lo = mid`. If you ever write `lo = mid` (not `lo = mid + 1`), round up. ## Putting it all together Binary search is O(log n) not because it's magic, but because it has one job: **shrink the search space by half at each step**. Everything else — the closed interval, the `mid ± 1`, the monotonic predicate — is in service of guaranteeing that the halving is always valid. When you see a problem, the tell for binary search isn't "is there a sorted array?" — it's "can I define a space of candidates and a check that tells me, in one shot, whether to go left or right?" If yes, you have an O(log n) solution hiding in what might look like a brute-force problem. For more on how search fits into the broader picture, see the [searching crash course](/dsa/crash-course/06-searching). The sorted array structure that makes all of this work is covered in [arrays](/dsa/structures/arrays). And if you want the tree-based alternative that also gives you O(log n) search (with dynamic insertions), see [binary search trees](/dsa/structures/binary-search-tree). ## Frequently asked questions Q: Why does binary search require a sorted array? A: Binary search works by comparing the middle element to your target and then discarding half the remaining elements. That only works if you can guarantee all smaller values are to the left and all larger values are to the right — which sorted order gives you. On an unsorted array you have no way to know which half to discard, so you cannot safely eliminate anything. Q: How do you avoid off-by-one errors in binary search? A: Pick an invariant and stick to it. The most reliable approach: keep the search space as a closed interval [lo, hi] where both endpoints are valid candidates. Loop while lo <= hi. Compute mid = lo + (hi - lo) // 2. After comparing, move lo to mid + 1 or hi to mid - 1 — inside this loop, moving a boundary to mid itself risks an infinite loop. The first-true template used for search-on-the-answer is different: it pairs while lo < hi with hi = mid, which is safe because mid is always strictly below hi. Q: What is "binary search on the answer"? A: Instead of searching for a value in an array, you binary search over the range of possible answers to find the smallest (or largest) value that satisfies some condition. The condition must be monotonic — once it becomes true, it stays true as you increase the candidate value. Classic examples: minimum speed to eat all bananas, minimum days to ship all packages, minimum capacity for a split into k subarrays. Q: How do you find the first or last occurrence of a value with binary search? A: When you find the target at mid, do not stop — keep narrowing the search toward the left (for first occurrence) or right (for last occurrence). For first: set hi = mid - 1 and record mid as a candidate. For last: set lo = mid + 1 and record mid. The loop still runs in O(log n) because you always move a boundary. Q: Can binary search work on an infinite or very large search space? A: Yes. Binary search on the answer often operates over a huge numeric range — 1 to 10^9 or 1 to 10^18 — rather than over an array. You just need a monotonic feasibility function and upper/lower bounds on the possible answer. Because each iteration halves the range, even a range of 10^18 takes only about 60 iterations.