Binary Search
What Is Binary Search?
Binary search is a divide-and-conquer algorithm that locates a target in a sorted array by repeatedly halving the search space. At each step it compares the target with the middle element:
- ›Target equals middle → found
- ›Target is smaller → search the left half
- ›Target is larger → search the right half
Sorted array: [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]
0 1 2 3 4 5 6 7 8 9
Target: 23
Step 1: lo=0, hi=9, mid=4 → arr[4]=16 < 23 → search right half → lo=5
Step 2: lo=5, hi=9, mid=7 → arr[7]=45 > 23 → search left half → hi=6
Step 3: lo=5, hi=6, mid=5 → arr[5]=23 = 23 → FOUND at index 5 ✓
Linear search would need 6 comparisons to find 23.
Binary search found it in 3 comparisons.
For n=1024: linear ≈ 512 avg, binary ≈ 10.
Core Invariant
Understanding why binary search works requires understanding its invariant:
At every iteration, the target — if it exists — is guaranteed to be inside the range [lo, hi] inclusive. When lo > hi, the range is empty — target is not in the array. Why this invariant holds: Initial: entire array [0, n-1] — target could be anywhere ✓ arr[mid] < target: target must be in (mid, hi] → lo = mid + 1 ✓ arr[mid] > target: target must be in [lo, mid) → hi = mid - 1 ✓ arr[mid] == target: found — invariant no longer needed ✓
Iterative Binary Search
1public class BinarySearch {
2
3 // Standard iterative binary search — returns index or -1
4 public static int binarySearch(int[] arr, int target) {
5 int lo = 0, hi = arr.length - 1;
6
7 while (lo <= hi) {
8 int mid = lo + (hi - lo) / 2; // Overflow-safe midpoint
9
10 if (arr[mid] == target) {
11 return mid; // Found
12 } else if (arr[mid] < target) {
13 lo = mid + 1; // Target in right half
14 } else {
15 hi = mid - 1; // Target in left half
16 }
17 }
18
19 return -1; // Not found — lo > hi, range is empty
20 }
21
22 public static void main(String[] args) {
23 int[] arr = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72};
24
25 System.out.println(binarySearch(arr, 23)); // 5
26 System.out.println(binarySearch(arr, 2)); // 0 — leftmost element
27 System.out.println(binarySearch(arr, 72)); // 9 — rightmost element
28 System.out.println(binarySearch(arr, 10)); // -1 — not found
29 System.out.println(binarySearch(arr, 100)); // -1 — beyond range
30
31 // Single-element array
32 int[] single = {42};
33 System.out.println(binarySearch(single, 42)); // 0
34 System.out.println(binarySearch(single, 5)); // -1
35 }
36}Output:
5
0
9
-1
-1
Dry Run: Iterative Binary Search
arr = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72] (indices 0–9) target = 23 Iteration 1: lo=0, hi=9 mid = 0 + (9-0)/2 = 4 arr[4] = 16 < 23 → lo = mid+1 = 5 Iteration 2: lo=5, hi=9 mid = 5 + (9-5)/2 = 7 arr[7] = 45 > 23 → hi = mid-1 = 6 Iteration 3: lo=5, hi=6 mid = 5 + (6-5)/2 = 5 arr[5] = 23 = 23 → return 5 ✓ Total comparisons: 3 Linear search average for this element: 6 ──────────────────────────────────────── target = 10 (not in array) Iteration 1: lo=0, hi=9, mid=4, arr[4]=16 > 10 → hi=3 Iteration 2: lo=0, hi=3, mid=1, arr[1]=5 < 10 → lo=2 Iteration 3: lo=2, hi=3, mid=2, arr[2]=8 < 10 → lo=3 Iteration 4: lo=3, hi=3, mid=3, arr[3]=12 > 10 → hi=2 lo=3 > hi=2 → loop ends → return -1 ✓
Recursive Binary Search
1public class RecursiveBinarySearch {
2
3 public static int binarySearch(int[] arr, int target) {
4 return search(arr, target, 0, arr.length - 1);
5 }
6
7 private static int search(int[] arr, int target, int lo, int hi) {
8 if (lo > hi) return -1; // Base case: empty range
9
10 int mid = lo + (hi - lo) / 2;
11
12 if (arr[mid] == target) return mid;
13 else if (arr[mid] < target) return search(arr, target, mid + 1, hi); // Right half
14 else return search(arr, target, lo, mid - 1); // Left half
15 }
16
17 public static void main(String[] args) {
18 int[] arr = {1, 3, 5, 7, 9, 11, 13};
19 System.out.println(binarySearch(arr, 7)); // 3
20 System.out.println(binarySearch(arr, 6)); // -1
21 System.out.println(binarySearch(arr, 1)); // 0
22 System.out.println(binarySearch(arr, 13)); // 6
23 }
24}Output:
3
-1
0
6
Iterative vs Recursive — Which to Use?
Iterative: No call stack overhead No risk of stack overflow for large arrays Preferred in production and interviews Space: O(1) Recursive: More readable — mirrors the mathematical definition Uses O(log n) call stack space Risk of stack overflow for very deep recursion (rarely an issue for sorted arrays since log₂(10⁹) ≈ 30 — well within stack limits) Space: O(log n) Default recommendation: iterative. Use recursive only if recursion depth is not a concern and readability matters more.
Variant 1: Find First Occurrence
When duplicates exist, standard binary search may return any matching index. To find the leftmost (first) occurrence, continue searching the left half even after a match.
1public class FirstOccurrence {
2
3 public static int firstOccurrence(int[] arr, int target) {
4 int lo = 0, hi = arr.length - 1, result = -1;
5
6 while (lo <= hi) {
7 int mid = lo + (hi - lo) / 2;
8
9 if (arr[mid] == target) {
10 result = mid; // Record this potential answer
11 hi = mid - 1; // But keep searching LEFT for an earlier one
12 } else if (arr[mid] < target) {
13 lo = mid + 1;
14 } else {
15 hi = mid - 1;
16 }
17 }
18
19 return result;
20 }
21
22 public static void main(String[] args) {
23 int[] arr = {1, 2, 2, 2, 3, 4, 5};
24
25 System.out.println(firstOccurrence(arr, 2)); // 1 (first of three 2s)
26 System.out.println(firstOccurrence(arr, 3)); // 4
27 System.out.println(firstOccurrence(arr, 6)); // -1
28 }
29}Output:
1
4
-1
Variant 2: Find Last Occurrence
Mirror of first occurrence — continue searching the right half after a match.
1public class LastOccurrence {
2
3 public static int lastOccurrence(int[] arr, int target) {
4 int lo = 0, hi = arr.length - 1, result = -1;
5
6 while (lo <= hi) {
7 int mid = lo + (hi - lo) / 2;
8
9 if (arr[mid] == target) {
10 result = mid; // Record and keep searching RIGHT
11 lo = mid + 1;
12 } else if (arr[mid] < target) {
13 lo = mid + 1;
14 } else {
15 hi = mid - 1;
16 }
17 }
18
19 return result;
20 }
21
22 // Count occurrences using first and last position
23 public static int countOccurrences(int[] arr, int target) {
24 int first = FirstOccurrence.firstOccurrence(arr, target);
25 if (first == -1) return 0;
26 int last = lastOccurrence(arr, target);
27 return last - first + 1;
28 }
29
30 public static void main(String[] args) {
31 int[] arr = {1, 2, 2, 2, 3, 4, 5};
32
33 System.out.println(lastOccurrence(arr, 2)); // 3 (last of three 2s)
34 System.out.println(lastOccurrence(arr, 5)); // 6
35 System.out.println(lastOccurrence(arr, 6)); // -1
36 System.out.println(countOccurrences(arr, 2)); // 3
37 System.out.println(countOccurrences(arr, 4)); // 1
38 }
39}Output:
3
6
-1
3
1
Dry Run: First and Last Occurrence of 2 in [1,2,2,2,3,4,5]
arr = [1, 2, 2, 2, 3, 4, 5] (indices 0-6) target = 2 ── FIRST OCCURRENCE ────────────────────────────── lo=0, hi=6, result=-1 Iter 1: mid=3, arr[3]=2 == 2 → result=3, hi=mid-1=2 (search left) Iter 2: lo=0, hi=2, mid=1, arr[1]=2 == 2 → result=1, hi=0 Iter 3: lo=0, hi=0, mid=0, arr[0]=1 < 2 → lo=1 lo=1 > hi=0 → stop. result=1 ✓ ── LAST OCCURRENCE ─────────────────────────────── lo=0, hi=6, result=-1 Iter 1: mid=3, arr[3]=2 == 2 → result=3, lo=mid+1=4 (search right) Iter 2: lo=4, hi=6, mid=5, arr[5]=4 > 2 → hi=4 Iter 3: lo=4, hi=4, mid=4, arr[4]=3 > 2 → hi=3 lo=4 > hi=3 → stop. result=3 ✓ Count: last - first + 1 = 3 - 1 + 1 = 3 ✓
Variant 3: Integer Square Root
Problem: Find the integer square root of n — the largest integer x such that x² ≤ n.
Binary search on the answer: The answer lies in [0, n]. Use binary search on this range.
1public class IntegerSqrt {
2
3 public static int mySqrt(int n) {
4 if (n < 2) return n;
5
6 int lo = 1, hi = n / 2, result = 0; // Answer is ≤ n/2 for n ≥ 4
7
8 while (lo <= hi) {
9 long mid = lo + (hi - lo) / 2L; // Long to avoid mid*mid overflow
10 long sq = mid * mid;
11
12 if (sq == n) {
13 return (int) mid; // Perfect square
14 } else if (sq < n) {
15 result = (int) mid; // This mid qualifies — search right
16 lo = (int) mid + 1;
17 } else {
18 hi = (int) mid - 1;
19 }
20 }
21
22 return result;
23 }
24
25 public static void main(String[] args) {
26 System.out.println(mySqrt(4)); // 2 — perfect square
27 System.out.println(mySqrt(8)); // 2 — floor(√8) = 2 (2²=4 ≤ 8, 3²=9 > 8)
28 System.out.println(mySqrt(9)); // 3
29 System.out.println(mySqrt(2)); // 1
30 System.out.println(mySqrt(1)); // 1
31 System.out.println(mySqrt(0)); // 0
32 }
33}Output:
2
2
3
1
1
0
The Overflow-Safe Midpoint
Common mistake: int mid = (lo + hi) / 2; Problem: If lo = 2_000_000_000 and hi = 2_000_000_001 (both near Integer.MAX_VALUE): lo + hi = 4_000_000_001 > Integer.MAX_VALUE (2_147_483_647) → integer overflow → mid becomes a negative number → infinite loop Overflow-safe version: int mid = lo + (hi - lo) / 2; Why it's safe: hi - lo is always ≥ 0 and ≤ MAX_VALUE (since hi ≥ lo and both ≤ MAX_VALUE) (hi - lo) / 2 is always ≤ MAX_VALUE / 2 lo + (hi - lo) / 2 ≤ lo + (MAX_VALUE - lo) / 2 < MAX_VALUE ✓ Alternative (uses unsigned right shift in Java/JavaScript): int mid = (lo + hi) >>> 1; // Java/JS: unsigned right shift avoids sign bit
Built-in Binary Search
1import java.util.*;
2
3public class BuiltinBinarySearch {
4
5 public static void main(String[] args) {
6 int[] arr = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72};
7
8 // Arrays.binarySearch — returns index if found, -(insertionPoint)-1 if not found
9 System.out.println(Arrays.binarySearch(arr, 23)); // 5
10 System.out.println(Arrays.binarySearch(arr, 10)); // -4 (insertion point = 3)
11 // Negative result means: -(insertionPoint) - 1 = -4 → insertionPoint = 3
12
13 // Decode insertion point from negative result
14 int result = Arrays.binarySearch(arr, 10);
15 int insertAt = result >= 0 ? result : -(result + 1);
16 System.out.println("Insert at: " + insertAt); // 3
17
18 // Collections.binarySearch for Lists
19 List<Integer> list = Arrays.asList(2, 5, 8, 12, 16, 23, 38, 45, 56, 72);
20 System.out.println(Collections.binarySearch(list, 38)); // 6
21 }
22}Common Mistakes
Using lo < hi instead of lo <= hi as the loop condition. With lo < hi, the loop exits when lo == hi — one element remains unchecked. If the target is at that single-element position, it is missed. Always use lo <= hi so the single-element case is handled.
Using hi = mid instead of hi = mid - 1. When arr[mid] > target, the target is in [lo, mid-1] — mid itself is excluded. Using hi = mid (instead of mid - 1) leaves mid in the search space. If arr[mid] is always greater than target, mid never advances and the loop runs forever.
Not using the overflow-safe midpoint. (lo + hi) / 2 overflows when both lo and hi are close to Integer.MAX_VALUE. Always use lo + (hi - lo) / 2 in Java and C++. In Python this is not an issue since integers are arbitrary-precision.
Returning lo instead of -1 when the target is not found. After the loop ends with lo > hi, lo is the insertion point — the index where target would be inserted to maintain sorted order. Returning lo can be useful (lower bound), but for "is target present?" always return -1 explicitly.
Forgetting that Arrays.binarySearch in Java returns a negative value (not -1) when not found. The return value is -(insertionPoint) - 1. Comparing the result to -1 misses cases where the target is not found but the insertion point is not 0.
Interview Questions
Q: Why does binary search need a sorted array?
Binary search eliminates half the search space at each step by comparing the target to the middle element and deciding which half it cannot be in. This decision is only valid if the array is sorted — in a sorted array, if arr[mid] < target, the target cannot be in [lo, mid]. In an unsorted array, a smaller middle element gives no information about where the target might be. The entire algorithm's correctness rests on the sorted-order guarantee.
Q: What is the exact worst-case number of comparisons for binary search on n elements?
⌊log₂(n)⌋ + 1 comparisons. For n=8: ⌊log₂(8)⌋ + 1 = 3 + 1 = 4. For n=1024: ⌊log₂(1024)⌋ + 1 = 10 + 1 = 11. Each comparison either returns the answer or halves the search space, so after k comparisons at most 1 element remains, requiring one final check.
Q: How does finding the first occurrence differ from standard binary search?
Standard binary search returns the moment it finds any match. Finding the first occurrence records the match but sets hi = mid - 1 to continue searching the left half for an earlier match. The result is updated on every match found — after the loop ends, result holds the leftmost index of the target, or -1 if never found. The asymptotic complexity remains O(log n) — the loop still terminates in at most ⌊log₂(n)⌋ + 1 iterations.
FAQs
Can binary search work on a descending sorted array?
Yes — swap the comparison directions. When arr[mid] > target, search the right half (lo = mid + 1); when arr[mid] < target, search the left half (hi = mid - 1). The algorithm works on any monotonically ordered sequence as long as the comparison direction matches the ordering.
Why use hi = arr.length - 1 and not arr.length?
The standard template uses an inclusive range [lo, hi] where both endpoints are valid array indices. With hi = arr.length - 1, the initial range covers the entire array [0, n-1]. Some templates use an exclusive upper bound hi = arr.length with lo < hi — this is equally valid but requires different update rules. The inclusive template (lo <= hi, hi = mid - 1) is simpler to reason about for standard search.
Is binary search always faster than linear search?
For a single search on an already-sorted array, yes — O(log n) vs O(n). But if the array must be sorted first (O(n log n)), and only one search is performed, linear search is faster overall. For k searches on the same array: binary search wins when k × O(log n) < O(n log n) + k × O(log n), which is always true since sorting is a one-time cost. Always sort once and binary search many times when repeated searches are needed.
Summary
Binary search finds a target in a sorted array in O(log n) time by halving the search space at every step.
The iterative template — three lines to remember:
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
Critical rules:
- ›Loop condition:
lo <= hi— notlo < hi - ›Midpoint:
lo + (hi - lo) / 2— not(lo + hi) / 2(overflow) - ›Updates:
lo = mid + 1andhi = mid - 1— notmid(infinite loop) - ›Not found: return
-1— notloor0
Variants by changing what happens on arr[mid] == target:
- ›Standard: return
midimmediately - ›First occurrence: set
result = mid, thenhi = mid - 1(continue left) - ›Last occurrence: set
result = mid, thenlo = mid + 1(continue right) - ›Answer on range: apply binary search to the answer space, not the array
Built-ins:
- ›Java:
Arrays.binarySearch(returns negative insertion point if not found) - ›Python:
bisect.bisect_left/bisect_right(returns insertion point) - ›C++:
lower_bound,upper_bound(returns iterator),binary_search(returns bool) - ›JavaScript: no built-in — implement with the template above
In the next topic, you will explore Binary Search Patterns — applying binary search to non-obvious problems: searching on the answer space, peak finding, and monotonic condition problems.
What is the time complexity of binary search on a sorted array of n elements?