Binary Search in Java — Iterative, Recursive, and Collections.binarySearch()

Binary search finds a target in a sorted array in O(log n) time by repeatedly halving the search range.

Standard iterative version

low = 0, high = n - 1
while (low <= high) {
    mid = low + (high - low) / 2
    if arr[mid] == target: return mid
    if arr[mid] < target: low = mid + 1
    else: high = mid - 1
}
return -1

Critical correctness points

1. Overflow-safe mid

• (low + high) / 2 overflows if low + high > Integer.MAX_VALUE
• Use low + (high - low) / 2
• Famous JDK bug fixed in 2006

2. Loop condition

• low <= high — search range non-empty
• low < high — wrong; misses cases when low == high

3. Updates

• low = mid + 1 (not low = mid)
• high = mid - 1 (not high = mid)
• We've checked arr[mid] != target; skip it
• Without +1/-1: infinite loop when high = low + 1

Recursive version

• Same logic with recursion
• O(log n) stack space
• log₂(2^31) ≈ 31 — safe stack depth
• Iterative is just as clean; rare to choose recursive

Variants

Lower bound (first index >= target)

• high = n (not n-1)
• low < high (strict)
• high = mid (not mid - 1)
• Returns insertion point preserving sort order
• Useful for first occurrence, count of elements < target

Upper bound (first index > target)

• Similar; arr[mid] <= target advances low
• For last occurrence (subtract 1), count elements <= target

Range count

• count = upperBound(target) - lowerBound(target)
• Handles duplicates

Java built-ins

Arrays.binarySearch / Collections.binarySearch

• Requires sorted input
• Returns index if found
• Returns -(insertion_point) - 1 if not found
• For not-found: int ip = -result - 1

Caveats

• Doesn't return first/last for duplicates — just any match
• Use lower/upper bound for those
• LinkedList: O(n) due to traversal — don't use

With Comparator

• Collections.binarySearch(list, key, comparator)
• Comparator must match the sort order

Complex variants

Search in rotated sorted array

• O(log n)
• Determine which half is sorted
• Check if target is in that half

2D matrix search (sorted rows + cols)

• Walk from top-right
• Down if too small, left if too large
• O(m + n)

Find peak element

• Compare mid to mid+1
• Follow the gradient up
• O(log n)

Find min in rotated sorted array

• Compare mid to high
• O(log n)

Binary search the answer

• For monotone problems (find smallest x satisfying P(x))
• Examples: square root, capacity to ship, K-th smallest
• Search the answer space, not the array

Common bugs

1. Overflow

• (low + high) / 2 can overflow
• Use low + (high - low) / 2

2. Off-by-one

• Wrong loop condition
• Wrong updates (mid vs mid+1)
• Drawing the search range helps

3. Infinite loop

• low = mid without +1
• When high = low + 1, mid = low, no progress

4. Using on unsorted data

• Results undefined
• Sort first or use linear scan

5. Misunderstanding negative return

• Collections.binarySearch returns -(ip+1)
• Not -1; not 0
• ip = -result - 1

6. Wrong comparator

• Must match the sort order used
• Inconsistent comparator → wrong results

Performance

• Binary search: O(log n)
• Linear scan: O(n)
• Sort then binary search: O(n log n) — only worth it if many searches amortize the sort
• TreeMap / TreeSet: O(log n) per operation, no sort needed (always sorted)

For interviews

Standard binary search

• Iterative version
• Overflow-safe mid
• Correct loop condition and updates

Lower / upper bound

• For first/last occurrence with duplicates
• For range counts

Variants

• Rotated sorted, 2D matrix, peak, find min
• 'Binary search the answer' for monotone problems

Java APIs

• Arrays.binarySearch / Collections.binarySearch
• Insertion point convention

Recommendation: For binary search, always use the iterative version with the overflow-safe mid: int mid = low + (high - low) / 2 — the famous (low + high) / 2 overflow bug went undetected in Java's standard library for ~9 years. Use `low <= high` for the loop condition and `mid + 1` / `mid - 1` for updates to ensure progress and avoid infinite loops. For first or last occurrence with duplicates, use lower bound (first index >= target) or upper bound (first index > target) variants — these have slightly different invariants (high = n, low < high, high = mid). For Java's built-ins (Arrays.binarySearch, Collections.binarySearch), remember the insertion-point convention: returns -(insertion_point) - 1 if not found; compute int ip = -result - 1. Don't use Collections.binarySearch on a LinkedList (O(n) traversal cost). Know the classic variants: search in rotated sorted array (O(log n) by determining which half is sorted), 2D matrix search (O(m+n) walking from top-right), find peak element (O(log n) following gradient), and 'binary search the answer' for monotone problems (square root, capacity-to-ship, K-th smallest). For sorted maps/sets, prefer `TreeMap.ceilingKey/floorKey` over manual binary search — same O(log n) but more idiomatic. Always verify the input is sorted; binary search on unsorted data has undefined behavior. The mental model: binary search = halve the range each step using a comparison; if the comparison gives monotone information about where the answer can be, it works — not just for arrays but for any monotone search space.