Definition
- Binary search – an efficient algorithm that finds a target value in a sorted array by repeatedly halving the search range.
- Halving – each comparison eliminates half the remaining elements, giving O(log n) time complexity.
- Precondition – the data must be sorted; on unsorted data binary search gives wrong answers.
- Pointers – two indices,
lowandhigh, bound the active range and tighten each iteration. - Generalisation – the same halving idea finds insertion points, boundary positions, and answers to monotonic predicates.
Imagine looking up an account in the National Bank of India's register, which is sorted by account number. Instead of reading from page one, you open the book right in the middle. If the account you want is smaller than the middle one, you know it is in the first half, so you ignore the second half entirely and open the middle of the first half. You keep halving the book, and within a handful of jumps you land on the exact page. Compared to flipping every page, this is dramatically faster.
Understanding the Concepts
What is binary search?
Binary search is an algorithm that locates a target value inside a sorted collection by repeatedly dividing the search range in half. It maintains two pointers, low and high, that define the boundaries of the active range. At each step, it examines the middle element and decides whether to continue searching in the left half or the right half.
The key insight is that each comparison eliminates half of the remaining candidates. With one million elements, a linear scan might need one million comparisons, but binary search needs at most about twenty. This logarithmic scaling is what makes binary search indispensable for fast lookups.
package com.bank.search;
import java.math.BigDecimal;
public class AccountSearch {
/**
* Finds the index of targetBalance in a sorted array of account balances.
* Returns -1 if the balance is not present.
*/
public static int findBalance(BigDecimal[] balances, BigDecimal target) {
int low = 0;
int high = balances.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int cmp = balances[mid].compareTo(target);
if (cmp == 0) {
return mid; // found
} else if (cmp < 0) {
low = mid + 1; // target is in the right half
} else {
high = mid - 1; // target is in the left half
}
}
return -1; // not found
}
public static void main(String[] args) {
BigDecimal[] balances = {
new BigDecimal("10000.00"),
new BigDecimal("25000.00"),
new BigDecimal("50000.00"),
new BigDecimal("75000.00"),
new BigDecimal("100000.00")
};
BigDecimal target = new BigDecimal("50000.00");
int index = findBalance(balances, target);
System.out.println("Balance " + target + " found at index: " + index);
}
}
Balance 50000.00 found at index: 2
Why does binary search exist?
Linear search checks every element one by one and takes O(n) time. For small collections this is fine, but as data grows to thousands or millions of entries the cost becomes prohibitive. Binary search exists to exploit the sorted order of data and deliver answers in O(log n) time.
In banking, the National Bank of India maintains a sorted ledger of account numbers for every branch. When a teller needs to verify whether an account exists, a linear scan through hundreds of thousands of accounts would be unacceptably slow. Binary search gives the answer in about 17 comparisons for 100,000 accounts.
package com.bank.search;
public class WhyBinarySearch {
public static void main(String[] args) {
int n = 100_000;
int maxComparisons = (int) Math.ceil(Math.log(n) / Math.log(2));
System.out.println("Elements: " + n);
System.out.println("Linear search worst case: " + n + " comparisons");
System.out.println("Binary search worst case: " + maxComparisons + " comparisons");
}
}
Elements: 100000
Linear search worst case: 100000 comparisons
Binary search worst case: 17 comparisons
How does binary search work internally?
Binary search starts with low = 0 and high = array.length - 1. It computes the midpoint as mid = low + (high - low) / 2, which avoids integer overflow that can occur with (low + high) / 2 when both values are large.
- It compares the element at
midwith the target: - If they are equal, the search is complete.
- If the target is larger, the left half including
midis discarded by settinglow = mid + 1. - If the target is smaller, the right half including
midis discarded by settinghigh = mid - 1.
The loop runs while low <= high. When the pointers cross, the target is absent.
package com.bank.search;
public class BinarySearchSteps {
public static int searchWithTrace(long[] accountNumbers, long target) {
int low = 0;
int high = accountNumbers.length - 1;
int step = 0;
while (low <= high) {
step++;
int mid = low + (high - low) / 2;
System.out.println("Step " + step + ": low=" + low
+ " high=" + high + " mid=" + mid
+ " value=" + accountNumbers[mid]);
if (accountNumbers[mid] == target) {
System.out.println("Found at index " + mid);
return mid;
} else if (accountNumbers[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
System.out.println("Not found after " + step + " steps");
return -1;
}
public static void main(String[] args) {
long[] accounts = {1001, 1025, 1050, 1080, 1100, 1150, 1200, 1250};
searchWithTrace(accounts, 1150);
}
}
Step 1: low=0 high=7 mid=3 value=1080
Step 2: low=4 high=7 mid=5 value=1150
Found at index 5
Why must the midpoint use low + (high - low) / 2?
The expression (low + high) / 2 can overflow when low and high are both large positive integers. In Java, int holds values up to about 2.1 billion. If low = 1_500_000_000 and high = 2_000_000_000, their sum exceeds Integer.MAX_VALUE and wraps to a negative number, producing a wrong index.
The safe form low + (high - low) / 2 computes the difference first, which never overflows when both values are non-negative, and then adds the half-difference to low.
package com.bank.search;
public class MidpointOverflow {
public static void main(String[] args) {
int low = 1_500_000_000;
int high = 2_000_000_000;
int naiveMid = (low + high) / 2; // WRONG: overflow
int safeMid = low + (high - low) / 2; // CORRECT
System.out.println("Naive mid: " + naiveMid); // negative number
System.out.println("Safe mid: " + safeMid); // correct value
}
}
Naive mid: -397483648
Safe mid: 1750000000
What is the precondition for binary search?
The absolute precondition is that the data must be sorted. Binary search assumes that if the middle element is smaller than the target, then all elements to the left of the middle are also smaller, so they can be safely discarded. If the data is unsorted, this assumption breaks and binary search produces wrong results silently.
package com.bank.search;
import java.util.Arrays;
public class UnsortedTrap {
public static void main(String[] args) {
int[] unsorted = {50, 20, 80, 10, 40};
// Arrays.binarySearch on unsorted data: result is undefined
int result = Arrays.binarySearch(unsorted, 40);
System.out.println("Result on unsorted: " + result + " (unreliable)");
Arrays.sort(unsorted);
result = Arrays.binarySearch(unsorted, 40);
System.out.println("Result on sorted: " + result + " (correct)");
}
}
Result on unsorted: -3 (unreliable)
Result on sorted: 2 (correct)
How does Java provide binary search in its standard library?
Java offers Arrays.binarySearch for arrays and Collections.binarySearch for lists. Both require the input to be sorted in ascending natural order, or by a provided Comparator. They return the index if found, or -(insertion point) - 1 if not found.
package com.bank.search;
import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class JavaLibrarySearch {
public static void main(String[] args) {
// Array binary search
long[] accountNumbers = {1001, 1025, 1050, 1080, 1100};
int idx = Arrays.binarySearch(accountNumbers, 1050);
System.out.println("Array search for 1050: index " + idx);
int missing = Arrays.binarySearch(accountNumbers, 1060);
System.out.println("Array search for 1060: " + missing
+ " (insert at " + (-(missing) - 1) + ")");
// List binary search with Comparator
List<BigDecimal> balances = List.of(
new BigDecimal("10000"), new BigDecimal("25000"),
new BigDecimal("50000"), new BigDecimal("75000")
);
int listIdx = Collections.binarySearch(balances, new BigDecimal("25000"));
System.out.println("List search for 25000: index " + listIdx);
}
}
Array search for 1050: index 2
Array search for 1060: -4 (insert at 3)
List search for 25000: index 1
What are common mistakes with binary search?
The most frequent mistakes are the midpoint overflow, using < instead of <= in the loop condition, and forgetting to move pointers past mid.
Using while (low < high) instead of while (low <= high) misses the case where low == high and the target is at that single remaining index. Forgetting mid + 1 or mid - 1 can cause the loop to spin forever because the range never shrinks.
package com.bank.search;
public class CommonMistakes {
// WRONG: uses < instead of <=
public static int buggySearch(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low < high) { // BUG: misses single-element range
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1; // misses target when low == high
}
// CORRECT: uses <=
public static int correctSearch(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) { // CORRECT
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50};
System.out.println("Buggy finds 50: " + buggySearch(arr, 50));
System.out.println("Correct finds 50: " + correctSearch(arr, 50));
}
}
Buggy finds 50: -1
Correct finds 50: 4
How does binary search generalise beyond exact matching?
The halving idea adapts to find the insertion point for a new element, the first or last occurrence of a duplicate, or the boundary in a monotonic predicate. These variations form the basis of the lower-bound, upper-bound, and binary-search-on-the-answer patterns used heavily in competitive programming and production systems.
In databases, B-tree index lookups are binary search applied to sorted pages, which is why a sorted index makes queries fast.
package com.bank.search;
public class LowerBound {
/** Returns the index of the first element >= target. */
public static int lowerBound(long[] arr, long target) {
int low = 0, high = arr.length;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
public static void main(String[] args) {
long[] accounts = {1001, 1025, 1025, 1025, 1050, 1080};
int lb = lowerBound(accounts, 1025);
System.out.println("Lower bound of 1025: index " + lb
+ " value=" + accounts[lb]);
}
}
Lower bound of 1025: index 1 value=1025
What is the time and space complexity?
Binary search runs in O(log n) time because each step halves the range. The space complexity is O(1) for the iterative version because it uses only a few integer variables. The recursive version uses O(log n) stack space.
| Metric | Iterative | Recursive |
|---|---|---|
| Time | O(log n) | O(log n) |
| Space | O(1) | O(log n) |
| Stack overflow risk | None | Possible on huge arrays |
package com.bank.search;
public class ComplexityDemo {
public static void main(String[] args) {
int[] sizes = {1_000, 1_000_000, 1_000_000_000};
for (int n : sizes) {
int steps = (int) Math.ceil(Math.log(n) / Math.log(2));
System.out.println("n=" + String.format("%,d", n)
+ " -> max steps=" + steps);
}
}
}
n=1,000 -> max steps=10
n=1,000,000 -> max steps=20
n=1,000,000,000 -> max steps=30
When should you use binary search and when should you not?
Use binary search when data is sorted, randomly accessible (arrays, not linked lists), and queried repeatedly. The O(log n) payoff justifies keeping data sorted.
Do not use binary search on unsorted data, linked lists where you cannot jump to the middle, or when you search only once and the sort cost O(n log n) exceeds the linear scan cost O(n). For frequent lookups without ordering needs, a HashMap with O(1) average time often beats both.
package com.bank.search;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class WhenToUse {
public static void main(String[] args) {
long[] accounts = {1080, 1001, 1050, 1025, 1100};
// One-off search: linear scan is cheaper than sort + binary search
boolean found = false;
for (long a : accounts) {
if (a == 1050) { found = true; break; }
}
System.out.println("Linear one-off: " + found);
// Repeated searches: sort once, binary search many times
Arrays.sort(accounts);
System.out.println("Binary repeated: "
+ (Arrays.binarySearch(accounts, 1050) >= 0));
// Frequent lookups: HashMap is O(1) average
Map<Long, Boolean> map = new HashMap<>();
for (long a : accounts) map.put(a, true);
System.out.println("HashMap lookup: " + map.containsKey(1050L));
}
}
Linear one-off: true
Binary repeated: true
HashMap lookup: true
What are common interview follow-up questions?
Interviewers frequently extend binary search into these directions:
- Find the first or last occurrence in a sorted array with duplicates.
- Find the insertion position for a missing element.
- Search in a rotated sorted array.
- Find the peak element in a mountain array.
- Binary search on the answer: find the minimum capacity, speed, or threshold.
- Validate a binary search tree using range bounds.
Each of these builds on the same halving template but adjusts how the midpoint comparison drives the pointer movement.
Visual Overview
Sorted array: [1001, 1025, 1050, 1080, 1100, 1150, 1200, 1250]
0 1 2 3 4 5 6 7
Target: 1150
Step 1: low=0 mid=3 high=7
[1001, 1025, 1050, 1080, 1100, 1150, 1200, 1250]
^^^^
1080 < 1150 -> move low to mid+1 = 4
Step 2: low=4 mid=5 high=7
[ ... , 1100, 1150, 1200, 1250]
^^^^
1150 == 1150 -> FOUND at index 5
Binary Search Decision Tree (3 elements):
arr[1]
/ \
< target > target
/ \
arr[0] arr[2]
/ \ / \
found absent found absent
Key Takeaway
Binary search is an efficient algorithm for finding a target in a sorted array by repeatedly halving the search range. You keep two pointers, low and high, that bound the current range. You look at the middle element: if it matches the target you are done, if the target is smaller you discard the right half, and if it is larger you discard the left half. Because every comparison eliminates half of the remaining elements, binary search runs in O(log n) time, which is dramatically faster than the O(n) linear scan it replaces.
The non-negotiable precondition is that the data must be sorted. On unsorted data binary search gives wrong answers silently. The midpoint must be computed as low + (high - low) / 2 rather than (low + high) / 2, because the naive form can overflow when the indices are large, a famous bug that lurked in standard libraries for years.
In a banking system at the National Bank of India, binary search powers fast lookups over sorted arrays of account numbers. With a million accounts, a linear scan could take a million comparisons, but binary search needs only about twenty. Java provides Arrays.binarySearch and Collections.binarySearch out of the box, both requiring sorted input.
The senior-level insight is that binary search generalises far beyond exact matching. The same halving idea finds insertion points, first and last occurrences among duplicates, and boundaries of monotonic conditions. In databases, B-tree index lookups are binary search applied to sorted pages, which is why maintaining a sorted index makes queries fast.
Remember one sentence: binary search halves a sorted range at each step, finding any target in about log-base-two-of-n comparisons.
---