Binary Search
Throw away half of what's left with every look — a million items in 20 steps.
▶ guided lesson⚡ 1-minute summary↻ 14 recall cards
before this: Arrays & Strings · Big-O · Two Pointers
01 · why it exists
Why this exists, and the weight it carries
since1946 · 1960
Binary search
John Mauchly (first mention); D. H. Lehmer (first version for any n)
Binary search was first mentioned by John Mauchly in the 1946 Moore School Lectures, the first course on building electronic computers — as Knuth records in The Art of Computer Programming, Vol. 3. Early published versions only worked when the table had 2ᵏ − 1 entries; D. H. Lehmer published one that works for any n in 1960. It stayed tricky: in Jon Bentley's courses at Bell Labs and IBM, about 90% of professional programmers found bugs in their own binary search (Programming Pearls).
the problem it solvedFinding an item among n sorted ones with about log₂ n comparisons instead of up to n.
its jobs today
Arrays.binarySearch,Collections.binarySearch, and lookups in any sorted array: sorted ID lists, symbol tables, sorted logs.git bisect: the Git docs describe it as using "a binary search algorithm" to find the commit that introduced a bug.- Debugging by halves: disable half the config, half the input, half the code — then the half that still fails.
the weight it carries
Illustrative: 10 lakh (10⁶) sorted order IDs. Linear scan: up to 1,000,000 comparisons. Binary search: at most ⌊log₂ 10⁶⌋ + 1 = 20. At 10⁹ items it's still only 30.
without it
Every lookup in sorted data would be a full scan; finding a bad commit among 1,000 would take up to 1,000 test runs instead of about 10.
when · why · how
- when
- The data is sorted (or a yes/no test flips exactly once) and you need fast lookups — usually many of them.
- why
- O(log n) per lookup with O(1) extra space. Sorting first costs O(n log n) once, so it pays off as soon as you search more than a handful of times.
- how
Arrays.binarySearch(a, key)to ask "is it there?"; a hand-writtenwhile (lo <= hi)loop withmid = lo + (hi - lo) / 2when you need control.
since1994
Lower bound & upper bound (boundary search)
Alexander Stepanov & Meng Lee (the names, in the C++ STL)
Searching for the first position where a condition turns true is as old as binary search itself.
The names lower_bound and upper_bound come from Stepanov and Lee's Standard Template Library report at HP Labs (1994): the first and the last position where a value can be inserted without breaking the order, each in at most log₂ n + 1 comparisons.
Java never added them for arrays; TreeSet.ceiling and higher answer the same questions for a sorted set.
the problem it solvedHandling duplicates and missing values: first and last occurrence, counts, and insert positions — all in O(log n).
its jobs today
- Range counts on sorted data: how many orders between two timestamps = lowerBound(end + 1) − lowerBound(start).
- Insert in order and "where would it go?":
Arrays.binarySearchreturns that insertion point, encoded as −(point) − 1. - Every "first index where…" question: First Bad Version, the minimum of a rotated array, binary search on the answer.
the weight it carries
Illustrative: a sorted log of 10⁶ timestamps where one busy second holds 50,000 entries. "Find any match, then walk left and right": up to 50,000 steps. Lower bound + upper bound: 2 × 20 = 40 comparisons, however many duplicates there are.
without it
Duplicates would force a linear walk after every hit, turning O(log n) into O(n) on skewed data.
when · why · how
- when
- The question is about a position — first, last, how many, where to insert — or the data has duplicates.
- why
- Always O(log n): the
lo < hiloop never stops early, so duplicates don't slow it down. O(1) extra space. - how
lo = 0, hi = n; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] >= x) hi = mid; else lo = mid + 1; }— use>for upper bound.
since2006
The overflow-safe midpoint
Joshua Bloch
java.util.Arrays.binarySearch computed its midpoint from low + high. For arrays of more than about 2³⁰ (1.07 billion) elements, that sum can pass 2³¹ − 1 and wrap negative.
The bug was filed as JDK-5045582 and fixed in JDK 6. On 2 June 2006, Bloch — who wrote that method — explained it in "Nearly All Binary Searches and Mergesorts are Broken", after it had waited about nine years.
The same bug sat in the binary search of Bentley's Programming Pearls. His fixes: low + ((high - low) / 2) or (low + high) >>> 1; JDK 17 uses the second.
the problem it solvedA midpoint that stays correct for every array size and every value range up to Integer.MAX_VALUE.
its jobs today
- Every binary search over large indices or value ranges: First Bad Version (n up to 2³¹ − 1), Koko's speeds, capacities.
- The JDK itself:
Arrays.binarySearchcomputesint mid = (low + high) >>> 1;.
the weight it carries
Illustrative: First Bad Version with n = 2³¹ − 1 = 2,147,483,647. After one step lo = 1,073,741,825 and hi = 2,147,483,647. lo + hi = 3,221,225,472 doesn't fit in an int: it wraps to −1,073,741,824, and mid becomes −536,870,912. lo + (hi − lo) / 2 gives 1,610,612,736.
without it
Searches pass every small test, then crash (ArrayIndexOutOfBoundsException) or loop forever on the one huge input in production.
when · why · how
- when
- Every time you write
mid— make it a habit, not a special case. - why
- It costs one subtraction and removes a whole class of overflow bugs:
hi − loalways fits when 0 ≤ lo ≤ hi. - how
int mid = lo + (hi - lo) / 2;— or(lo + hi) >>> 1when both are non-negative. Uselongif lo can be negative and the range is wider than an int.
since?
Binary search on the answer
Searching a range of possible answers with a yes/no test is the integer cousin of the bisection method from numerical analysis, and is folklore in programming contests; we found no single inventor to credit.
its jobs today
git bisectagain: "is this commit bad?" flips once along the history, so each test run halves the suspects.- Capacity planning: the fewest servers, the biggest batch size or the shortest timeout that still passes a load test — each check is one experiment.
the weight it carries
Illustrative: Koko with speeds 1..10⁹ and 10⁴ piles. Trying every speed: up to 10⁹ × 10⁴ = 10¹³ pile checks. Binary search: ⌈log₂ 10⁹⌉ = 30 guesses × 10⁴ = 3·10⁵.
without it
"Minimum capacity such that…" questions would need a scan over up to 10⁹ candidates, or a special formula for each problem.
when · why · how
- when
- The question asks for the smallest (or largest) value that works, and "works" is monotonic — once true, it stays true as the value grows.
- why
- O(C · log R) for an answer range R and a check costing C, instead of O(C · R). The check is usually one greedy pass.
- how
- Write
boolean ok(int x)first, thenwhile (lo < hi) { int mid = lo + (hi - lo) / 2; if (ok(mid)) hi = mid; else lo = mid + 1; }and return lo.
02 · plain english
The idea in 30 seconds
Look at the middle of what's left. One comparison tells you which half cannot hold the answer — throw that half away.
Halving n until 1 is left takes about log₂ n steps: 1,000,000 items → 20 looks, 1,000,000,000 → 30.
It works on anything monotonic: a sorted array, or any yes/no question that flips from no to yes exactly once.
picture this
Finding "Priya" in a sorted contact list of 1,000 names without scrolling: jump to the middle (say "Meera"). Priya comes later, so the whole first half is gone. Jump to the middle of what's left, and again — about 10 jumps, never 1,000.
03 · remember
What you must know
- Binary search needs a monotonic property: sorted values, or a yes/no test that goes
no no no yes yes yes. Not sorted? Then you need some other reason to discard a half (rotated arrays, peaks). - Keep a search space and an invariant — a sentence that is always true about it, like "if the target exists, it is inside [lo, hi]". Every update must keep the sentence true.
- Template 1 — find exactly:
lo = 0, hi = n−1, while (lo <= hi), move withlo = mid + 1/hi = mid − 1. Stops when the space is empty. - Template 2 — find a boundary:
lo = 0, hi = n, while (lo < hi), move withhi = mid/lo = mid + 1. Stops when one candidate is left; that candidate is the answer. - Compute
mid = lo + (hi − lo) / 2. The tempting(lo + hi) / 2overflows whenlo + hi > 2³¹ − 1— a real bug that sat in the JDK for years. - Lower bound = first index with
a[i] >= x; upper bound = first index witha[i] > x. Count of x = upper − lower. First/last occurrence and insert position all fall out of these two. Arrays.binarySearch/Collections.binarySearchreturn the index if found, otherwise-(insertionPoint) − 1— always negative. With duplicates, which match you get is not specified.- Binary search on the answer: when the question is "smallest speed / capacity / time that works" and bigger always works if smaller does, binary search the answer range and test each guess with a fast greedy check.
04 · see it
Play with it in 3D
Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.
Classic binary search — watch the space halve
Grey cells are ruled out for good. Count the looks: never more than ⌊log₂ n⌋ + 1.
Lower bound with lo < hi
With duplicates, keep shrinking towards the *first* match. `hi = mid` keeps mid alive because it might be the answer.
Search in a rotated sorted array
One side of mid is always sorted (pink). Check whether the target fits inside it; if not, it must be on the other side.
Find the minimum after rotation
Compare mid with the right end: bigger means the cliff is to the right.
Find a peak — binary search without sorting
Walking uphill must end at a peak. The slope at mid tells you which half surely has one.
Binary search on the answer — Koko's speed
The bottom row is the *answer space* (speeds), not the input. Each guess is tested with a quick O(n) check.
05 · cost
Time & space, explained
| Time | Extra space | why | |
|---|---|---|---|
| Linear scan | O(n) | O(1) | Might have to look at every element; ignores the sorted order completely. |
| Binary search (iterative) | O(log n) | O(1) | Each look halves the space: n → n/2 → … → 1 takes ⌊log₂ n⌋ + 1 looks at most. |
| Binary search (recursive) | O(log n) | O(log n) | Same looks, but each one adds a stack frame — log n frames deep. |
| Lower / upper bound | O(log n) | O(1) | Same halving; it just doesn't stop early on a match. |
| First + last occurrence (two bounds) | O(log n) | O(1) | Two binary searches = 2·log n, still O(log n) — even if the value fills the whole array. |
Arrays.binarySearch(int[], key) | O(log n) | O(1) | The JDK's iterative binary search on a primitive array. |
Collections.binarySearch on ArrayList | O(log n) | O(1) | ArrayList is RandomAccess, so get(mid) is O(1). |
Collections.binarySearch on LinkedList | O(n) | O(1) | Only O(log n) comparisons, but walking the links to each mid costs O(n) traversal in total. |
| Sort once, then q searches | O(n log n + q log n) | O(log n) | Sorting dominates once; worth it as soon as you search more than a handful of times. |
| Time | Extra space | why | |
|---|---|---|---|
| General: range R, check costs C | O(C · log R) | O(1) | log R guesses, each verified by one call to the check. |
| Koko Eating Bananas (LC 875) | O(n log M) | O(1) | M = largest pile. Each guess sums ⌈pile / speed⌉ over n piles. |
| Ship Packages (LC 1011) | O(n log S) | O(1) | S = total weight. Each guess simulates loading the ship in one pass. |
| Median of Two Sorted Arrays (LC 4) | O(log min(m, n)) | O(1) | We binary search how many elements the shorter array puts in the left half. |
| Try every candidate instead | O(C · R) | O(1) | R can be 10⁹ — this is the brute force that binary search on the answer replaces. |
06 · java
Raw vs Collections Framework
Find one value: write it vs call the library
class Classic { /** Returns an index of target in the sorted array, or -1 if it is not there. */ static int search(int[] nums, int target) { int lo = 0, hi = nums.length - 1; // search space [lo, hi], both inclusive while (lo <= hi) { // space is non-empty while lo <= hi int mid = lo + (hi - lo) / 2; // overflow-safe middle if (nums[mid] == target) return mid; if (nums[mid] < target) lo = mid + 1; // target can only be right of mid else hi = mid - 1; // target can only be left of mid } return -1; // space became empty: not present }}class Library { /** Index of key, or where it would be inserted to keep the array sorted. */ static int indexOrInsertion(int[] sorted, int key) { int i = Arrays.binarySearch(sorted, key); // found → index; missing → -(insertionPoint) - 1 return i >= 0 ? i : -i - 1; // decode the negative result } static int indexOrInsertion(List<Integer> sorted, int key) { int i = Collections.binarySearch(sorted, key); // same contract; O(log n) only for RandomAccess lists return i >= 0 ? i : -i - 1; }}- Not found → the library returns
-(insertionPoint) − 1. Decode it with-i − 1. The−1is there so that "insert at 0" (−1) is still negative. - With duplicates the library may return any matching index. Need the first or last one? Write a lower/upper bound yourself.
- The array must already be sorted (and by the same comparator). On unsorted input the result is simply undefined — no exception.
Collections.binarySearchon aLinkedListis O(n): only use it onArrayListor otherRandomAccesslists.
Boundaries: lower bound and upper bound
class Bounds { /** First index i with nums[i] >= target, or nums.length if there is none. */ static int lowerBound(int[] nums, int target) { int lo = 0, hi = nums.length; // answer is in [lo, hi]; hi = n means "none" while (lo < hi) { // stop when exactly one candidate is left int mid = lo + (hi - lo) / 2; if (nums[mid] >= target) hi = mid; // mid might be the answer: keep it else lo = mid + 1; // mid is too small: drop it } return lo; // lo == hi: the boundary } /** First index i with nums[i] > target, or nums.length if there is none. */ static int upperBound(int[] nums, int target) { int lo = 0, hi = nums.length; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] > target) hi = mid; else lo = mid + 1; } return lo; } /** How many times target appears = upperBound - lowerBound. */ static int count(int[] nums, int target) { return upperBound(nums, target) - lowerBound(nums, target); }}hi = nums.length(notn − 1) because "no element qualifies" is a valid answer: index n.hi = mid(notmid − 1) because mid passed the test and might be the answer.lo = mid + 1because mid failed.- The loop ends when
lo == hi— exactly one candidate, no extra check needed. - Java has no
lowerBoundfor arrays. For a changing sorted collection useTreeSet.ceiling(x)(first ≥ x) andTreeSet.higher(x)(first > x), both O(log n).
The overflow-safe midpoint
class Midpoint { static int naive(int lo, int hi) { return (lo + hi) / 2; } // lo + hi can overflow int static int safe(int lo, int hi) { return lo + (hi - lo) / 2; } // hi - lo always fits static int unsigned(int lo, int hi) { return (lo + hi) >>> 1; } // the JDK's trick (needs lo, hi >= 0)}lo + hican exceedInteger.MAX_VALUE(2,147,483,647) once indices or values pass ~1.07 billion — the sum wraps negative.lo + (hi − lo) / 2never overflows when0 ≤ lo ≤ hi. Use it everywhere; it costs nothing.- The JDK uses
(lo + hi) >>> 1: the unsigned shift reads the wrapped sum correctly. Only valid when both are non-negative. - Searching over values that can be negative (e.g.
lo = -10⁹)?lo + (hi − lo) / 2is still safe as long ashi − lofits — uselongif it might not.
Binary search on the answer
class OnAnswer { /** * Smallest x in [lo, hi] with ok(x) true, where ok looks like * false false ... false true true ... true (monotonic). Returns hi if only hi works. */ static int firstTrue(int lo, int hi, IntPredicate ok) { while (lo < hi) { int mid = lo + (hi - lo) / 2; if (ok.test(mid)) hi = mid; // mid works: the answer is mid or smaller else lo = mid + 1; // mid fails: everything <= mid fails too } return lo; } /** Example: integer square root = largest x with x*x <= n = firstTrue(x*x > n) - 1. */ static int isqrt(int n) { int hi = Math.min(n, 46340) + 1; // 46341² already exceeds Integer.MAX_VALUE return firstTrue(0, hi, x -> (long) x * x > n) - 1; }}- This is lower bound on an imaginary array:
ok(lo), ok(lo+1), …readsfalse … false true … true. - Write
ok(x)first, as a normal greedy function. Then wrap it in this loop. Interviewers love seeing the two pieces separately. - Use
longinsideokwhen you add up many values — sums of 10⁴ items of size 10⁹ overflowint.
| call | does | cost |
|---|---|---|
Arrays.binarySearch(int[] a, int key) | Index of key, or -(insertionPoint) − 1 if absent | O(log n) |
Arrays.binarySearch(a, from, to, key) | Same, on the range [from, to) — to is exclusive | O(log(to − from)) |
Arrays.binarySearch(T[] a, key, cmp) | Objects sorted by a comparator | O(log n) comparisons |
Collections.binarySearch(list, key) | Same contract for a sorted List | O(log n) on ArrayList, O(n) on LinkedList |
TreeSet.ceiling(x) / floor(x) | Smallest element ≥ x / largest ≤ x (null if none) | O(log n) |
TreeSet.higher(x) / lower(x) | Smallest element > x / largest < x | O(log n) |
TreeMap.ceilingKey(x) / floorKey(x) | Bound queries on map keys | O(log n) |
(p + k - 1L) / k | ⌈p / k⌉ for positive p, k, computed in long (Math.ceilDiv only arrived in Java 18 — not in Java 17) | O(1) |
Does x exist in a fixed sorted array?
→ Arrays.binarySearch
One line, tested, O(log n).
First / last position, count, or insert index with duplicates
→ Hand-written lower / upper bound
The library gives some match, not the first one.
Sorted data that keeps changing (insert/delete + nearest value)
→ TreeSet / TreeMap ceiling / floor
A sorted array costs O(n) per insert; a red-black tree keeps every operation O(log n).
"Minimum X such that it is possible"
→ Binary search on the answer + greedy check
Turns an O(R) scan of candidates into O(log R).
Search a List<Integer>
→ Collections.binarySearch on an ArrayList
Never on a LinkedList — getting to the middle is O(n).
07 · recognise
Spot the pattern
Input is sorted (or each row of a matrix is) and you need O(log n)
Classic binary search or lower/upper bound
"First", "last", "insert position", "how many equal to x"
Lower bound / upper bound (lo < hi template)
"Minimum capacity / speed / time / largest minimum such that …"
Binary search on the answer with a greedy feasibility check
Sorted array that was rotated
Compare mid with an end to find which half is sorted
"Find any peak" or local min/max in O(log n)
Follow the slope at mid
Constraints like n ≤ 10⁵ with values up to 10⁹, and an O(n) check is easy
O(n log V) — binary search over the value range
Two sorted arrays, k-th smallest / median
Binary search on a partition of the shorter array
An expensive yes/no check that flips once ("is this version bad?", "does this build pass?")
Find the first true with the lo < hi template — fewest calls
"k closest values to x" in a sorted array
The answer is a window: binary search its start in [0, n − k]
08 · traps & tricks
Mistakes to avoid, tricks to use
traps
- Infinite loop: using
lo = midwithmid = lo + (hi − lo) / 2in alo < hiloop. Whenhi = lo + 1, mid == lo and nothing moves. Either uselo = mid + 1, or round mid up (lo + (hi − lo + 1) / 2). - Mixing templates:
while (lo < hi)withhi = mid − 1, orwhile (lo <= hi)withhi = mid. Pick one template and keep all three parts consistent. - Starting
hiatn − 1when the answer can ben(insert at the end, "none found"). (lo + hi) / 2overflow on large indices or value ranges.- Reading
Arrays.binarySearch's negative result as "not found = −1". It's-(insertionPoint) − 1, so it can be −1, −2, −7… - Calling binary search on unsorted data. It won't crash — it just silently returns garbage.
- Binary search on the answer with a non-monotonic check: if "works" can flip back to "doesn't work", halving is invalid.
- Integer overflow inside the check: a total of hours can pass 2³¹ − 1 at slow speeds (3 piles of 805,306,368 at speed 1 = 2,415,919,104), and
(p + k − 1)only just fits for p, k ≤ 10⁹. Do the check's arithmetic inlong.
tricks
- Before coding, say the invariant out loud: "The answer is always in [lo, hi]". Then each update line is just "keep that true".
- Dry-run the 2-element case (
[a, b]). Almost every off-by-one or infinite-loop bug shows up there. - Default to the
lo < hiboundary template for anything that isn't "is x present?". It never needs a separateansvariable. - Think "array of booleans":
F F F T T T. Lower bound, rotated min, Koko, shipping — they are all "find the first T". - Say the complexity of a binary-search-on-answer solution as O(check × log range) — e.g. "O(n log 10⁹), about 30 passes over the array".
- When unsure whether to return
loorhi: in thelo < hitemplate they're equal at the end. In thelo <= hitemplate,lois the insert position.
09 · why & how
Questions you might be too shy to ask
Why is binary search O(log n)?
Each look cuts the remaining candidates in half. Starting from n, after k looks n/2ᵏ are left. You stop at 1, so k = log₂ n. Doubling the input adds just one more step.
Does the array have to be sorted?
It needs a reason to discard half. Sorted order is the most common reason, but rotated arrays (one half is always sorted), peaks (walk uphill), and yes/no answer spaces (once it works, bigger also works) all qualify. The real requirement is monotonicity of whatever you test at mid.
The input is sorted. Should I always reach for binary search?
Not always. Binary search finds one value or one boundary. If you need pairs (Two Sum II on a sorted array), two pointers is O(n), while a binary search per element is O(n log n). If you must look at every element anyway (like summing them), halving buys you nothing. Use it when one comparison can throw away half the candidates.
lo <= hi or lo < hi? I always mix them up.
Use lo <= hi (with hi = n − 1, moves mid ± 1) when you're looking for an exact match and can return from inside the loop. Use lo < hi (with moves hi = mid / lo = mid + 1) when you're narrowing down to a boundary — the loop ends with exactly one candidate. Both are correct; mixing their pieces is what breaks.
In the classic template, why mid + 1 and mid − 1? Why not just mid?
Because mid is already checked. If nums[mid] != target, mid can't be the answer, so throw it out too. lo = mid + 1 and hi = mid − 1 shrink the window every single time. With hi = mid here, once lo == hi == mid and nums[mid] > target, nothing changes — infinite loop. The boundary template is different: there mid might be the answer, so hi = mid keeps it on purpose.
How do I avoid infinite loops?
Make sure the space shrinks every iteration. With mid rounded down, lo = mid + 1 always shrinks, and hi = mid shrinks because mid < hi. The dangerous combination is lo = mid with mid rounded down. If you truly need lo = mid, round up: mid = lo + (hi − lo + 1) / 2.
Lower bound vs upper bound — I keep confusing them.
Lower bound = first index with value ≥ x. Upper bound = first index with value > x. In [1, 2, 2, 2, 5] with x = 2: lower = 1, upper = 4, so 2 appears 4 − 1 = 3 times. If x is missing (x = 3), both are 4: the count is 0, and 4 is where 3 would go. In code, the only difference is >= vs > in the test.
What if there are duplicates?
Classic search returns some matching index. If the problem cares which one (first, last, how many), use lower bound and upper bound. Rotated arrays with duplicates (LC 81, LC 154) degrade to O(n) in the worst case because nums[lo] == nums[mid] == nums[hi] tells you nothing.
Why does Arrays.binarySearch return -(insertionPoint) − 1 instead of just −1?
So one call gives you both answers: found (≥ 0) or where it would go (decode with -r − 1). The extra − 1 makes sure insertion point 0 still comes back negative (−1), so it can't be confused with "found at index 0".
Recursive or iterative?
Iterative. Same O(log n) time but O(1) space instead of O(log n) stack, and fewer chances to forget a return. Recursive is fine to explain the idea.
What does "binary search on the answer" actually mean?
You don't search the input array. You search the range of possible answers (speeds 1..max, capacities max..sum). For a guess, you run a quick greedy check: "can it be done with this?". If yes, try smaller; if no, try bigger. It works because the check is monotonic.
Binary search on the answer: how do I pick lo and hi?
lo = the smallest answer that could possibly work. hi = an answer that surely works. Koko: lo = 1 (speed 0 eats nothing and divides by zero), hi = the biggest pile (one pile per hour always fits, since h ≥ n). Ship: lo = the heaviest box (a smaller ship can't carry it), hi = the sum (everything in one day). If hi might fail, the real answer could sit outside your range.
Koko: why does hi = mid give the minimum speed, not just some speed that works?
Because a working mid is never thrown away. hoursAt(piles, mid) <= h → hi = mid: keep mid, and keep looking for something slower on its left. A failing mid → lo = mid + 1: it's out for good. The range always holds the first working speed, and the loop stops when one candidate is left. With piles = [3, 6, 7, 11], h = 8: speeds 1–3 fail, 4 and up work, so the search lands on 4.
Find Peak Element: the array isn't sorted. Won't binary search miss a peak?
It may skip some peaks — and that's fine, because the problem wants any peak. The rule only promises that the half you keep surely has one. If nums[mid] < nums[mid + 1], climb right: the climb can't go on forever, because past the end is −∞. In [1, 2, 1, 3, 5, 6, 4] the search returns index 5 (the value 6) and never looks at the peak at index 1 (the value 2) — both answers are accepted.
I understand binary search when I read it, but I mess it up when I write it. What now?
Very common — reading is easy, writing needs reps. Close the solution and write lower bound from memory on paper, without running it. Then check it by hand on [5] and [5, 7] with targets 4, 5, 6 and 8. Fix it, and write it again tomorrow. After 3–4 days the template comes out by itself — bas phir every new problem is just a new test at mid.
10 · practice
Interview problems
Every problem has brute → better → optimal solutions in Java, with complexity and a dry run.
- #704
- #35
- #34Find First and Last Position of Element in Sorted Arraymust-doMediumMetaLinkedInAppleBloombergAmazon+1
- #74Search a 2D MatrixMediumAmazonMicrosoftBloombergGoogleMeta+1
- #33
- #153
- #875
- #1011Capacity To Ship Packages Within D DaysMediumAmazonMetaGoogle
- #162
- #4Median of Two Sorted ArraysHardAdobeGoldman SachsBloombergAmazonMicrosoft+1
- #278
- #658Find K Closest ElementsMediumMetaAmazonGoogleMicrosoft
Also practise this here
Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.
- #69Sqrt(x)Easyin Big-O
Binary search on the answer in its smallest form: the largest r with r·r ≤ x — mind the overflow in r·r.
- #528Random Pick with WeightMediumin Math & Numbers
Prefix sums plus a lower-bound search pick an index in O(log n).
- #300Longest Increasing SubsequenceMediumin Dynamic Programming
The O(n log n) version keeps a sorted
tailsarray and binary searches it for every value. - #729My Calendar IMediumin BST
When the sorted data keeps changing,
TreeMap.floorKey/ceilingKeygive lower/upper-bound answers in O(log n).
11 · revise
The whole chapter on one screen
8 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.
- what it is
Look at the middle and throw away the half that can't hold the answer. n → n/2 → … → 1 takes about log₂ n looks: 20 for a million.
- use it when
Sorted data, or any yes/no test that flips once (
F F F T T T): first/last position, rotated arrays, peaks, "minimum speed that works". - template
Exact:
hi = n − 1,while (lo <= hi), movemid ± 1. Boundary:hi = n,while (lo < hi),hi = midorlo = mid + 1, return lo. - cost
O(log n) time, O(1) space (iterative). On the answer: O(check × log range) — about 30 checks for a range of 10⁹.
- trap
(lo + hi) / 2overflows past 2³¹ − 1. Writelo + (hi − lo) / 2— the JDK itself carried this bug for about nine years. - trap
lo = midwith a rounded-down mid loops forever when hi = lo + 1. Uselo = mid + 1, or round mid up. - trap
Arrays.binarySearchreturns-(insertion point) − 1when missing, and any copy among duplicates. Need first/last? Use lower/upper bound. - pro tip
Say the invariant out loud — "the answer is always in [lo, hi]" — and dry-run a 2-element array before you trust the loop.
12 · recall
Flip, remember, repeat
Why does binary search need only about log₂ n looks?
Question 1: Why does binary search need only about log₂ n looks?
13 · check yourself
Quick quiz
About how many looks does binary search need, at most, for 1,000,000 sorted items?
Why write `mid = lo + (hi - lo) / 2` instead of `(lo + hi) / 2`?
`Arrays.binarySearch(new int[]{10, 20, 30}, 25)` returns…
In the `while (lo < hi)` template you find nums[mid] satisfies the condition. Which update is correct for lower bound?
Which problem is NOT solved by "binary search on the answer"?
Rotated array [6, 7, 1, 2, 3, 4, 5]: lo = 0, hi = 6, mid = 3 (value 2). Which half is sorted?
Find Peak Element: nums[mid] = 4, nums[mid + 1] = 9. Where is a peak guaranteed?
Time complexity of Koko Eating Bananas with binary search (n piles, largest pile M)?
First Bad Version with n = 2³¹ − 1: lo = 1,073,741,825 and hi = 2,147,483,647. What does `(lo + hi) / 2` give in Java?
14 · learn more
A second teacher, if you want one
- ▶ playlistBinary Search Beginner to Advanced | C++, Java, Python | Notes + Contest ↗Striver (take U forward) · EnglishFrom the basic loop to lower/upper bound, rotated arrays, and binary search on the answer (Koko, aggressive cows, book allocation), in small steps.
- ▶ playlistBinary Search | Interview Questions | Coding | Tutorials | Algorithm ↗Aditya Verma · HindiTrains you to spot binary search where it isn't obvious, on half-sorted arrays and on answer ranges, using one format.
- ✎ articleExtra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken ↗Joshua Bloch · Google Research blog · EnglishThe true story of `(low + high) / 2` overflowing inside Java's own Arrays.binarySearch. Read it and you'll write `low + (high - low) / 2` for life.