Algorithms
Binary Search Divide & Conquer
Binary search eliminates half the remaining search space with each comparison, achieving O(log n) time on any sorted, random-access collection. Its deceptively simple concept hides many subtle variants โ finding the exact element, the leftmost/rightmost occurrence, or searching on an implicit answer space โ making it one of the most frequently mis-implemented algorithms in interviews.
01
Section One ยท Foundation
What is Binary Search?
Binary search works by maintaining two pointers โ lo and hi โ that define the active search interval. Each iteration computes mid = lo + (hi - lo) / 2 (integer overflow-safe), compares arr[mid] with the target, and eliminates the half that cannot contain the answer. After at most โlogโ nโ iterations, the target is found or its absence is confirmed. The algorithm requires the input to be sorted (or monotonic in some predicate) and support O(1) random access.
Analogy: Think of using a dictionary. Instead of reading every word from "A" to "Z", you open to the middle and ask "is my word before or after this page?" โ then repeat on the remaining half. Seven questions can locate a word in a million-word dictionary (2ยฒโฐ โ 10โถ, so 20 questions max).
Key Characteristics
Precondition: sorted (or monotone)
โถ
Binary search only works when the search space has a monotone predicate โ sorted array, answer-space binary search, rotated sorted array.
O(1) random access
โถ
Requires jumping to
arr[mid] in O(1). Works on arrays, not linked lists. For linked lists use skip lists or binary search trees.Off-by-one is the #1 bug
โถ
Loop condition (
< vs <=), mid calculation, and boundary update (hi = mid vs hi = mid-1) must be consistent. Use the template that matches the invariant.Generalised to answer-space search
โถ
Many problems ask "find the minimum x such that condition(x) is true" โ binary search on the answer value, not an array index.
02
Section Two ยท Variants
Core Variants
Classic Search โ Find Exact Target
Return the index of the target or -1 if not present. Loop condition:
while (lo <= hi).| Step | Action | State After |
|---|---|---|
| 1 | Set lo = 0, hi = n-1 | Full array is search space |
| 2 | mid = lo + (hi-lo)/2; if arr[mid] == target return mid | Found: return index |
| 3 | If arr[mid] < target: lo = mid+1; else hi = mid-1 | Search space halved; repeat until lo > hi |
Tip: Always compute mid as
lo + (hi - lo) / 2 to avoid integer overflow. Java's built-in Arrays.binarySearch returns -(insertionPoint) - 1 when not found, not -1.Left Bound โ First Occurrence / Lower Bound
Find the leftmost index where
arr[index] >= target. Returns the insertion point if target is absent. Loop condition: while (lo < hi).| Step | Action | State After |
|---|---|---|
| 1 | Set lo = 0, hi = n (note: hi = n, not n-1) | Search includes potential insertion at end |
| 2 | mid = lo + (hi-lo)/2; if arr[mid] < target: lo = mid+1; else hi = mid | Invariant: answer โ [lo, hi] |
| 3 | Loop ends when lo == hi; verify arr[lo] == target | lo is the leftmost valid index |
Tip: This template is equivalent to C++
std::lower_bound. When lo == hi, check arr[lo] == target to distinguish "found" from "insertion point".Right Bound โ Last Occurrence / Upper Bound
Find the rightmost index where
arr[index] <= target. Used to count occurrences: rightBound - leftBound + 1.| Step | Action | State After |
|---|---|---|
| 1 | Set lo = 0, hi = n-1 | Full array in scope |
| 2 | mid = lo + (hi-lo+1)/2 (round up); if arr[mid] > target: hi = mid-1; else lo = mid | Rounding up prevents infinite loop when lo+1==hi |
| 3 | Loop ends when lo == hi; verify arr[lo] == target | lo is the rightmost valid index |
Tip: The key subtlety is rounding up for mid when shrinking from the right (
lo = mid), to avoid the infinite loop when lo + 1 == hi.Search in Rotated Sorted Array
One pivot rotation creates two sorted halves. Determine which half is sorted, check if target falls in it, then recurse on the correct half.
| Step | Action | State After |
|---|---|---|
| 1 | Compute mid; check if arr[lo..mid] is sorted: arr[lo] <= arr[mid] | Know which half is sorted |
| 2 | If sorted half contains target (target โ [arr[lo], arr[mid]]): search left half | lo or hi updated accordingly |
| 3 | Otherwise search right half; repeat until target found or lo > hi | O(log n) guaranteed |
Tip: The invariant is "at least one half is always cleanly sorted". Checking
arr[lo] <= arr[mid] tells you which half it is, then check if the target falls in that sorted range. Common Mistake: The most frequent binary search bug is an off-by-one in the loop condition or boundary update. Using
while (lo <= hi) with hi = mid (instead of hi = mid-1) creates an infinite loop. Always choose one consistent template and stick to it โ don't mix conventions.
03
Section Three ยท Visuals
Diagrams & Walkthroughs
Classic Binary Search โ Step by Step
Left Bound vs Right Bound
O(log n) Growth โ Why It's Powerful
04
Section Four ยท Code
Implementations
Classic binary search quick-reference โ click the button for all four variants in four languages.
// Classic Binary Search โ Java 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;
}
Binary Search โ Full Implementation
Java โ Classic, Left Bound, Right Bound, Rotated Array
public class BinarySearch {
// โโ Classic: exact match โโโโโโโโโโโโโโโโโโโโโ
public static int search(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;
}
// โโ Left bound: first index where arr[i] >= target โโ
public static int lowerBound(int[] arr, int target) {
int lo = 0, hi = arr.length; // hi = n, open interval
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo; // lo == hi == insertion point
}
// โโ Right bound: last index where arr[i] <= target โโ
public static 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 - 1; // last index with value <= target
}
// โโ Search in rotated sorted array โโโโโโโโโโ
public static int searchRotated(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;
// left half is sorted
if (arr[lo] <= arr[mid]) {
if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // right half is sorted
if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
// โโ Answer-space binary search template โโโโโ
// "Find minimum k such that condition(k) is true"
public static int answerSearch(int lo, int hi, java.util.function.IntPredicate cond) {
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (cond.test(mid)) hi = mid;
else lo = mid + 1;
}
return lo; // lo is minimum k satisfying condition
}
}
Python โ Classic, Lower Bound, Upper Bound, Rotated
import bisect
def binary_search(arr, target):
lo, hi = 0, len(arr) - 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
def lower_bound(arr, target):
"""First index where arr[i] >= target (or len(arr) if all less)"""
return bisect.bisect_left(arr, target) # built-in O(log n)
def upper_bound(arr, target):
"""Last index where arr[i] <= target"""
pos = bisect.bisect_right(arr, target)
return pos - 1 # -1 if all elements > target
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 sorted
if arr[lo] <= target < arr[mid]: hi = mid - 1
else: lo = mid + 1
else: # right sorted
if arr[mid] < target <= arr[hi]: lo = mid + 1
else: hi = mid - 1
return -1
def answer_search(lo, hi, condition):
"""Find minimum k in [lo,hi] such that condition(k) is True"""
while lo < hi:
mid = lo + (hi - lo) // 2
if condition(mid): hi = mid
else: lo = mid + 1
return lo
JavaScript โ Classic, Lower/Upper Bound, Rotated
// Classic search
function binarySearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = lo + ((hi - lo) >> 1);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
// Lower bound (first index where arr[i] >= target)
function lowerBound(arr, target) {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (arr[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
// Search in rotated sorted array
function searchRotated(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = lo + ((hi - lo) >> 1);
if (arr[mid] === target) return mid;
if (arr[lo] <= arr[mid]) {
if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
C# โ Classic, Lower/Upper Bound, Rotated, Answer-Space
using System;
public class BinarySearch {
public static int Search(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;
}
public static 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;
}
public static int SearchRotated(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;
if (arr[lo] <= arr[mid]) {
if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
public static int AnswerSearch(int lo, int hi, Func<int,bool> cond) {
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (cond(mid)) hi = mid; else lo = mid + 1;
}
return lo;
}
}
05
Section Five ยท Complexity
Time & Space Complexity
| Variant | Best | Average | Worst | Space |
|---|---|---|---|---|
| Classic Search | O(1) (mid hit) | O(log n) | O(log n) | O(1) iter / O(log n) rec |
| Left / Right Bound | O(1) | O(log n) | O(log n) | O(1) |
| Rotated Array Search | O(1) | O(log n) | O(log n) | O(1) |
| Answer-Space Search | O(1) | O(log(R-L)) | O(log(R-L)) | O(1) |
| Linear Search (baseline) | O(1) | O(n) | O(n) | O(1) |
Why O(log n)? Each iteration eliminates exactly half the remaining search space. Starting with n elements, after k iterations there are n/2แต elements remaining. Setting n/2แต = 1 gives k = logโ(n). The iterative version uses O(1) extra space; a recursive implementation uses O(log n) call stack.
Space Complexity Note
Binary search is one of the most space-efficient algorithms โ the iterative version uses only three integer variables (lo, hi, mid) regardless of input size. Always prefer the iterative form in space-constrained environments or on deep call stacks.
06
Section Six ยท Decision Guide
When to Use Binary Search
Use Binary Search When
- Input is sorted (or has a monotone predicate)
- Need O(log n) search in a sorted array vs O(n) linear
- Problem asks "minimum/maximum x such that โฆ" โ answer-space BS
- Counting occurrences of a value in a sorted array
Avoid Binary Search When
- Array is unsorted and sorting is too expensive
- Data structure doesn't support O(1) random access (linked list)
- Only a few elements โ O(n) scan is simpler and fast enough
Comparison vs Search Alternatives
| Method | Precondition | Time | Space | Best For |
|---|---|---|---|---|
| Binary Search โ this | Sorted array | O(log n) | O(1) | Fast range queries on static sorted data |
| Linear Search | None | O(n) | O(1) | Unsorted data or tiny arrays |
| Hash Map | None | O(1) avg | O(n) | Point lookups, membership checks |
| BST / TreeMap | None | O(log n) | O(n) | Dynamic sorted data with insert/delete |
| Segment Tree | None | O(log n) | O(n) | Range queries with updates |
07
Section Seven ยท Interview Practice
LeetCode Problems
Binary search problems test the ability to identify the sorted/monotone property, choose the correct template, and handle edge cases. The hardest problems require binary-searching on the answer value, not the array index.
- Easy#704 โ Binary Search โ Classic template: find target in sorted array, return -1 if absent.
- Easy#278 โ First Bad Version โ Answer-space BS: find leftmost version where isBadVersion() returns true.
- Easy#35 โ Search Insert Position โ Lower bound template: return index target would be inserted to maintain sort order.
- Medium#34 โ Find First and Last Position in Sorted Array โ Left + right bound both applied to find range of a value.
- Medium#33 โ Search in Rotated Sorted Array โ Rotated variant: determine sorted half, then recurse correctly.
- Medium#153 โ Find Minimum in Rotated Sorted Array โ Find pivot: the minimum is the only element smaller than its predecessor.
- Medium#74 โ Search a 2D Matrix โ Treat the mรn matrix as a flattened sorted 1D array of length m*n.
- Medium#162 โ Find Peak Element โ Binary search on slope: if arr[mid] < arr[mid+1], peak is on right half.
- Hard#410 โ Split Array Largest Sum โ Binary search on answer: "Can we split into m pieces all โค mid?" is monotone.
- Hard#4 โ Median of Two Sorted Arrays โ Binary search on partition point: O(log(min(m,n))) without merging.
Interview Pattern: When a problem asks for a minimum/maximum value satisfying a condition, always check if the condition is monotone (all False then all True). If it is, binary search on the answer space directly โ you don't even need an array. This pattern solves "allocate minimum bandwidth", "koko eating bananas", "capacity to ship packages" and dozens more.