Algorithms

Binary Search Fundamentals

Halve the search space with every comparison — O(log n) on sorted data. Binary search goes far beyond "find target in array" — it finds boundaries, minimises maximums, and solves any problem where the answer space is monotonic.

Foundations · Array · Linked List · Stack · Queue · HashMap · Binary Tree · BST · Heap · Trie · Graph · Sorting · Binary Search · Two Pointers · Sliding Window · Dynamic Prog.
01
Section One · Foundation

What is Binary Search?

n = 16 elements n/2 = 8 n/4 = 4 n/8 = 2 1 ← found! step 0 step 1 — halve step 2 — halve step 3 — halve step 4 — done log₂16 = 4

Binary search works on any sorted or monotonic structure: compare the middle element to the target, then discard the half that cannot contain the answer. Each step eliminates 50% of the remaining candidates, giving O(log n) time — 20 comparisons to search 1 million elements, 30 comparisons for 1 billion. The prerequisite is order: the data must be sorted, or the predicate must be monotonic (false-false-false-true-true-true). Binary search shows up in three patterns in interviews: (1) classic "find target in sorted array," (2) lower/upper bound — "find the first/last position of target," and (3) "binary search on the answer" — the answer space is monotonic and you binary search for the optimal value. Pattern 3 is the hardest to recognise but the most frequently tested at the medium/hard level. The biggest source of bugs is off-by-one errors in the loop condition and boundary updates — always use the lo < hi template with lo = mid + 1 or hi = mid to avoid infinite loops.

Analogy: The number-guessing game. "I'm thinking of a number between 1 and 100." You guess 50. "Too high." Now you know the answer is 1–49. Guess 25. "Too low." Now 26–49. Each guess eliminates half the range. In 7 guesses (log₂ 100 ≈ 7) you find any number — not 50 guesses with linear scan. Binary search IS this game, applied to any ordered search space.
02
Section Two · Mental Model

How It Thinks

Array is sorted — elements to the left of mid are ≤ mid, elements to the right are ≥ mid
▶
A single comparison with arr[mid] eliminates an entire half — search space shrinks from n to n/2 to n/4 ... to 1 in log n steps
Mid is calculated as lo + (hi - lo) / 2 instead of (lo + hi) / 2
▶
Prevents integer overflow when lo + hi exceeds Integer.MAX_VALUE — a classic bug in every language with fixed-size integers
The loop shrinks the range [lo, hi] until lo == hi (or lo > hi)
▶
When the loop exits, lo (or hi) points to the answer boundary — either the target itself or the insertion point
Lower bound: "find the first index where arr[i] ≥ target"
▶
When arr[mid] < target → lo = mid + 1 (answer is to the right); when arr[mid] ≥ target → hi = mid (mid might be the answer, don't skip it)
Binary search on the answer: the answer space [min, max] is monotonic — feasible(x) flips from false to true at some threshold
▶
Binary search finds that threshold without checking every value — O(log(max-min) × cost_of_feasibility_check) total
Off-by-one errors come from inconsistent lo/hi updates and loop conditions
▶
Use ONE consistent template: while (lo < hi) with lo = mid + 1 and hi = mid — the loop terminates with lo == hi, the boundary
03
Section Three · Classic Search

Classic Binary Search — Find Exact Target

Find Target in Sorted Array
Return the index of target in a sorted array, or -1 if not found.
Pseudocode
function binarySearch(arr, target): lo = 0, hi = arr.length - 1 while lo <= hi: mid = lo + (hi - lo) / 2 if arr[mid] == target: return mid else if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1 // O(log n)
Binary Search — finding target = 7 in [1, 3, 5, 7, 9, 11, 13]
Step 1: lo=0, hi=6, mid=3 → arr[3]=7 == target ✓ 1 3 5 7 mid=3 9 11 13 lo=0 hi=6 FOUND at index 3 arr[mid] == 7 == target return mid = 3 Linear scan: checks 1, 3, 5, 7 → 4 comparisons Binary search: checks 7 → 1 comparison (lucky mid) Worst case for n elements: Linear = O(n) Binary = O(log n) For n = 1,000,000: linear = 1M checks, binary = 20 checks
The classic template uses lo <= hi with hi = mid - 1:
  • This three-way comparison (equal/less/greater) returns as soon as the target is found.
  • If the loop exits without finding the target, return -1.
  • This template works ONLY for exact-match search — for boundary-finding, use the lo < hi template in the next section.
04
Section Four · Bounds

Lower Bound & Upper Bound

Lower bound finds the first index where arr[i] ≥ target (leftmost insertion point). Upper bound finds the first index where arr[i] > target (rightmost insertion point). Together, they give you the range [lowerBound, upperBound) of all occurrences of target. This is the foundation of "Find First and Last Position of Element" (LC 34) and is more powerful than the classic search — it handles duplicates, insertion points, and boundary-finding in one consistent template.

Lower Bound

First index where arr[i] ≥ target

int lowerBound(int[] arr, int target) { int lo = 0, hi = arr.length; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] < target) lo = mid + 1; // too small else hi = mid; // could be answer } return lo; // first i: arr[i]≥target }
Upper Bound

First index where arr[i] > target

int upperBound(int[] arr, int target) { int lo = 0, hi = arr.length; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] <= target) lo = mid + 1; // ≤ is too small else hi = mid; // could be answer } return lo; // first i: arr[i]>target }
Lower and Upper Bound on [1, 3, 5, 5, 5, 7, 9] with target = 5
1 0 3 1 5 2 5 3 5 4 7 5 9 6 lower = 2 upper = 5 count of 5s = upper - lower = 5 - 2 = 3 lowerBound(5) → 2 first index where arr[i] ≥ 5 upperBound(5) → 5 first index where arr[i] > 5
The lo < hi template is the universal boundary finder:
  • The only thing that changes between lower bound and upper bound is the comparison — < target vs <= target.
  • When the loop exits, lo == hi and points to the boundary.
  • This single template handles: first occurrence, last occurrence, insertion point, and "search on answer" problems.
05
Section Five · Boundary Pattern

The Universal Boundary Template

Every binary search problem can be reduced to: "find the first index where condition(mid) is true." The condition splits the search space into [false, false, ..., false, true, true, ..., true]. Binary search finds the boundary between false and true. This abstraction unifies all binary search variants — exact match, lower bound, upper bound, rotated array search, and "search on answer" — into a single template.

The Universal Template
// Find FIRST index where condition(mid) is TRUE // Search space: [false, false, ..., false, TRUE, true, ..., true] // ↑ this is what we find int lo = MIN_POSSIBLE, hi = MAX_POSSIBLE; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (condition(mid)) hi = mid; // mid might be the answer — keep it else lo = mid + 1; // mid is definitely not — skip it } return lo; // lo == hi == first true index
Applying the Template
Problem condition(mid) lo hi
Lower bound (first ≥ target) arr[mid] >= target 0 n
Upper bound (first > target) arr[mid] > target 0 n
First occurrence of target arr[mid] >= target 0 n
Last occurrence of target arr[mid] > target → result - 1 0 n
Min speed to finish (LC 875) canFinish(mid) 1 max(piles)
Min capacity to ship (LC 1011) canShip(mid, days) max(weights) sum(weights)
The mental trick — reduce to yes/no:
  • Don't think "where is the target?" Think "at what point does the answer CHANGE from no to yes?" Binary search finds that transition point.
  • If you can formulate your problem as a monotonic boolean function, binary search applies — even when there's no array at all.
06
Section Six · Search on Answer

Binary Search on the Answer

The hardest-to-recognise binary search pattern: the answer itself is a number in a range [min, max], and there's a monotonic feasibility function — if answer x works, then x+1 also works (or vice versa). Instead of trying every possible answer linearly, binary search the answer space. The key insight: you're NOT searching an array — you're searching a range of possible answers, using a helper function to check "is this answer feasible?"

Example: Koko Eating Bananas (LC 875)
Koko eats bananas at speed k (bananas/hour). Given piles of bananas and h hours, find the minimum k such that she finishes all piles within h hours.
Pseudocode
function minEatingSpeed(piles, h): lo = 1 // minimum speed hi = max(piles) // maximum speed (eat biggest in 1h) while lo < hi: mid = lo + (hi - lo) / 2 if canFinish(piles, mid, h): // can she finish at speed mid? hi = mid // yes — try slower else: lo = mid + 1 // no — must go faster return lo // O(n × log(max)) function canFinish(piles, speed, h): hours = 0 for each pile in piles: hours += ceil(pile / speed) // hours needed for this pile return hours <= h
Binary search on answer — monotonic feasibility
speed = 1 speed = max canFinish = FALSE (too slow) canFinish = TRUE (fast enough) ANSWER minimum speed that works binary search finds this boundary in O(log(max)) steps
Signal for "binary search on the answer":
  • The problem asks to "minimize the maximum" or "find the minimum value such that ..." — and there's a yes/no feasibility check.
  • If you can write a function isFeasible(x) where the result is monotonic (all false then all true, or vice versa), binary search on x.
07
Section Seven · Pitfalls

Common Pitfalls & How to Avoid Them

The Four Deadliest Bugs
Bug Cause Fix
Integer overflow (lo + hi) / 2 overflows when lo + hi > INT_MAX Use lo + (hi - lo) / 2
Infinite loop lo = mid when mid = lo + (hi-lo)/2 rounds down — lo never advances Always use lo = mid + 1 in the lo < hi template. If you need hi = mid - 1, use mid = lo + (hi-lo+1)/2 (round up)
Off-by-one in hi Using hi = n - 1 vs hi = n — the answer might be "past the array" For lower/upper bound, set hi = n (past-the-end is a valid answer meaning "no element qualifies")
Wrong template Using lo <= hi for boundary search or lo < hi for exact match Exact match: lo <= hi + three-way if. Boundary: lo < hi + two-way if
Common Mistake: Mixing templates. The while (lo <= hi) template with hi = mid - 1 finds an exact match. The while (lo < hi) template with hi = mid finds a boundary. Using hi = mid in the lo <= hi loop causes an infinite loop. Pick one template and stick with it — the lo < hi boundary template covers all cases.
08
Section Eight · Implementation

Build It Once

Build all three variants (classic, lower bound, upper bound) once — and the "search on answer" pattern. In interviews, the lower bound template covers 90% of binary search problems.

Java — Binary Search core mechanics
// Classic — exact match — O(log n) int binarySearch(int[] arr, int target) { int lo = 0, hi = arr.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1; } // Lower bound — first i where arr[i] >= target — O(log n) int lowerBound(int[] arr, int target) { int lo = 0, hi = arr.length; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] < target) lo = mid + 1; else hi = mid; } return lo; } // Upper bound — first i where arr[i] > target — O(log n) int upperBound(int[] arr, int target) { int lo = 0, hi = arr.length; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] <= target) lo = mid + 1; else hi = mid; } return lo; }
09
Section Nine · Java Reference

Use It In Java

IN JAVA — Arrays.binarySearch() and Collections.binarySearch()
Array Arrays.binarySearch(arr, target) — returns index or -(insertion point) - 1
List Collections.binarySearch(list, target) — same return semantics
Import import java.util.Arrays; / import java.util.Collections;
Java built-in binary search patterns
// Basic search — returns index or negative int idx = Arrays.binarySearch(arr, target); if (idx < 0) { int insertionPoint = -(idx + 1); // where it would be inserted } // Search in a range int idx = Arrays.binarySearch(arr, fromIndex, toIndex, target); // ⚠ Java does NOT have lowerBound/upperBound built-in // You must write them yourself for: // - first/last occurrence // - count of elements in range // - search on answer problems // TreeMap/TreeSet have floor/ceiling which act like bounds TreeMap<Integer, String> map = new TreeMap<>(); map.floorKey(target); // largest key ≤ target map.ceilingKey(target); // smallest key ≥ target map.lowerKey(target); // largest key < target map.higherKey(target); // smallest key > target
Method Returns Note
Arrays.binarySearch(arr, x) index or -(insertPt)-1 Array MUST be sorted first
Collections.binarySearch(list, x) index or -(insertPt)-1 List MUST be sorted
TreeMap.floorKey(x) largest key ≤ x O(log n) — like lower bound
TreeMap.ceilingKey(x) smallest key ≥ x O(log n) — like lower bound
⚠ Gotcha: Arrays.binarySearch() does NOT guarantee which index is returned when there are duplicates — it just returns "an" index of the target, not the first or last. For "find first/last occurrence," you MUST write your own lower/upper bound. Don't rely on the built-in for boundary problems.
Choose Use Arrays.binarySearch() for simple "is target present?" checks. Write your own lower/upper bound for all interview problems — the 5-line template is easy to memorise and covers every binary search variant.
10
Section Ten · Practice

Problems To Solve

Binary search interview problems fall into three tiers: (1) classic search in a sorted array — easy, test template mastery; (2) modified search — rotated arrays, 2D matrices, peak finding — medium, test edge-case handling; (3) binary search on the answer — "minimise the maximum," "find minimum speed/capacity" — hardest to recognise, test problem-modelling ability. Tier 3 is where most candidates fail — not because the code is hard, but because they don't realise binary search applies.

Difficulty Pattern Problem Key Insight
Easy classic Binary Search — LC 704 Pure classic binary search on a sorted array. Use the lo <= hi template with three-way comparison. If you can't do this in 30 seconds, drill it.
Medium bounds Find First and Last Position — LC 34 Run lowerBound(target) for the first index, upperBound(target)-1 for the last. If lower bound doesn't point to target, return [-1,-1].
Medium rotated Search in Rotated Sorted Array — LC 33 At each step, one half is sorted. Check if target falls in the sorted half — if yes, search there; if no, search the other half. Key: compare arr[lo] with arr[mid] to find the sorted half.
Medium boundary Find Peak Element — LC 162 If arr[mid] < arr[mid+1], a peak exists to the right (go right). Otherwise go left. The binary search converges on a peak in O(log n). No need for sorted input — just monotonic local property.
Medium answer Koko Eating Bananas — LC 875 Binary search on speed [1, max(piles)]. For each speed, check if Koko can finish in h hours. Monotonic: higher speed → fewer hours. Find minimum speed where hours ≤ h.
Medium answer Capacity To Ship Packages — LC 1011 Binary search on capacity [max(weights), sum(weights)]. For each capacity, greedily count ships needed. Monotonic: higher capacity → fewer ships. Find minimum capacity for ≤ days ships.
Interview Pattern:
  • Every binary search problem reduces to "find the boundary where condition changes from false to true." For array problems, the condition involves arr[mid] vs target.
  • For "search on answer" problems, the condition is a feasibility function you write. Same template, different condition.
  • Master the lo < hi template with lo = mid + 1 / hi = mid — it solves every variant.

→ See all Binary Search problems with full solutions