Definition
- Binary search – a divide-and-conquer algorithm on a sorted array that repeatedly halves the search interval by comparing the target to the middle element.
- Midpoint calculation – use
mid = low + (high - low) / 2instead of(low + high) / 2to avoid integer overflow on large arrays. - Loop condition –
while (low <= high)ensures a single-element window is checked before the search concludes. - Discard logic – if
arr[mid] < target, the target is to the right, solow = mid + 1; ifarr[mid] > target, the target is to the left, sohigh = mid - 1. - Time complexity – O(log n) because each comparison halves the remaining range; O(1) space for the iterative form.
The National Bank of India has a ledger of accounts sorted by account number and Rajesh needs to find a specific one. Instead of reading every line, he opens the ledger in the exact middle. If the middle number is too high, the account must be in the left half, so he throws away the right half. If too low, he throws away the left half. He keeps halving until he lands on it, checking only a handful of pages even in a ledger of a million accounts.
Understanding the Concepts
What is binary search?
Binary search is the fundamental logarithmic-time algorithm for finding a target in a sorted array. It works by maintaining two bounds, low and high, that define the current search window, and on each step it looks at the middle element to decide which half to discard. Because each comparison eliminates half the remaining range, searching an array of n elements takes at most log2(n) steps.
At the National Bank of India, Rajesh authenticates customer logins by looking up account numbers stored in a sorted array. Binary search confirms whether an account exists and returns its index in about 20 steps for a million accounts.
package com.bank.core;
public class BinarySearch {
public static int search(int[] accounts, int target) {
int low = 0;
int high = accounts.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (accounts[mid] == target) {
return mid;
} else if (accounts[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] accounts = {1001, 1025, 1050, 1100, 1200, 1350, 1500};
int target = 1100;
int index = search(accounts, target);
System.out.println("Account " + target + " found at index: " + index);
}
}
Account 1100 found at index: 3
Why does binary search require sorted data?
The correctness of binary search depends entirely on the sorted order. When arr[mid] < target, we know the target cannot be anywhere to the left of mid because all those elements are even smaller. This lets us safely discard the entire left half. If the array were unsorted, the target could be anywhere and no comparison at mid would tell us which half to discard.
package com.bank.core;
import java.util.Arrays;
public class SortedPrecondition {
public static void main(String[] args) {
int[] unsorted = {1200, 1001, 1350, 1050, 1100};
int[] sorted = unsorted.clone();
Arrays.sort(sorted);
// Binary search on unsorted data gives wrong result
System.out.println("Unsorted search for 1100: " + Arrays.binarySearch(unsorted, 1100));
// Binary search on sorted data gives correct result
System.out.println("Sorted search for 1100: " + Arrays.binarySearch(sorted, 1100));
}
}
Unsorted search for 1100: -4
Sorted search for 1100: 2
How does the midpoint overflow bug work?
Computing (low + high) / 2 can overflow a 32-bit integer when both low and high are large. For example, if low = 1,500,000,000 and high = 2,000,000,000, their sum exceeds Integer.MAX_VALUE and wraps to a negative number. The safe form low + (high - low) / 2 avoids this because high - low is always non-negative and within range.
package com.bank.core;
public class MidpointOverflow {
public static void main(String[] args) {
int low = 1_500_000_000;
int high = 2_000_000_000;
int badMid = (low + high) / 2; // overflows
int goodMid = low + (high - low) / 2; // safe
System.out.println("Bad mid (overflow): " + badMid);
System.out.println("Good mid (safe): " + goodMid);
}
}
Bad mid (overflow): -397483648
Good mid (safe): 1750000000
What are common mistakes?
The most common mistake is using low < high instead of low <= high, which skips the check when the window shrinks to a single element. Another is forgetting the +1 or -1 on low and high updates, which causes an infinite loop when low == mid.
package com.bank.core;
public class BinarySearchMistakes {
// WRONG: low < high misses the single-element case
public static int searchBuggy(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low < high) { // Bug: should be low <= high
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
public static int searchCorrect(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
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 search for 50: " + searchBuggy(arr, 50));
System.out.println("Correct search for 50: " + searchCorrect(arr, 50));
}
}
Buggy search for 50: -1
Correct search for 50: 4
How is binary search different from linear search?
| Aspect | Linear Search | Binary Search |
|---|---|---|
| Precondition | None | Array must be sorted |
| Time complexity | O(n) | O(log n) |
| Steps for 1M elements | Up to 1,000,000 | At most 20 |
| Space complexity | O(1) | O(1) iterative, O(log n) recursive |
| Implementation | Simple loop | Needs careful midpoint and bounds |
package com.bank.core;
public class LinearVsBinary {
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
}
return -1;
}
public static int binarySearch(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
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[] accounts = {1001, 1025, 1050, 1100, 1200, 1350, 1500};
System.out.println("Linear: " + linearSearch(accounts, 1350));
System.out.println("Binary: " + binarySearch(accounts, 1350));
}
}
Linear: 5
Binary: 5
What about the recursive form?
Binary search can also be written recursively, where each call passes the narrowed bounds. The recursive form is cleaner to read but uses O(log n) stack frames, while the iterative form uses O(1) space.
package com.bank.core;
public class RecursiveBinarySearch {
public static int search(int[] arr, int target, int low, int high) {
if (low > high) return -1;
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) return search(arr, target, mid + 1, high);
return search(arr, target, low, mid - 1);
}
public static void main(String[] args) {
int[] accounts = {1001, 1025, 1050, 1100, 1200, 1350, 1500};
int result = search(accounts, 1200, 0, accounts.length - 1);
System.out.println("Recursive result: " + result);
}
}
Recursive result: 4
What are the edge cases?
Edge cases include searching an empty array, searching for a value smaller than the first element, searching for a value larger than the last element, and searching an array with a single element.
package com.bank.core;
public class BinarySearchEdgeCases {
public static int search(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
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) {
System.out.println("Empty array: " + search(new int[]{}, 5));
System.out.println("Below min: " + search(new int[]{10, 20, 30}, 5));
System.out.println("Above max: " + search(new int[]{10, 20, 30}, 50));
System.out.println("Single element found: " + search(new int[]{42}, 42));
System.out.println("Single element not found: " + search(new int[]{42}, 99));
}
}
Empty array: -1
Below min: -1
Above max: -1
Single element found: 0
Single element not found: -1
How does binary search generalize to answer-space search?
Beyond searching arrays, binary search applies to optimization problems where you search on the answer space. For example, finding the minimum interest rate that satisfies a loan constraint. You binary-search on the rate itself, checking at each midpoint whether the constraint is met, and halve the range accordingly. This pattern appears in problems like "minimum capacity to ship packages" and "split array largest sum."
package com.bank.core;
import java.math.BigDecimal;
import java.math.RoundingMode;
public class AnswerSpaceSearch {
// Find minimum monthly EMI that pays off a loan within maxMonths
public static BigDecimal findMinEmi(
BigDecimal principal, BigDecimal annualRate, int maxMonths) {
BigDecimal low = BigDecimal.ONE;
BigDecimal high = principal;
BigDecimal monthlyRate = annualRate.divide(
BigDecimal.valueOf(1200), 10, RoundingMode.HALF_UP);
while (high.subtract(low).compareTo(BigDecimal.valueOf(0.01)) > 0) {
BigDecimal mid = low.add(high).divide(
BigDecimal.valueOf(2), 10, RoundingMode.HALF_UP);
if (canPayOff(principal, monthlyRate, mid, maxMonths)) {
high = mid;
} else {
low = mid;
}
}
return high.setScale(2, RoundingMode.HALF_UP);
}
private static boolean canPayOff(
BigDecimal principal, BigDecimal rate, BigDecimal emi, int months) {
BigDecimal balance = principal;
for (int i = 0; i < months && balance.compareTo(BigDecimal.ZERO) > 0; i++) {
balance = balance.add(balance.multiply(rate)).subtract(emi);
}
return balance.compareTo(BigDecimal.ZERO) <= 0;
}
public static void main(String[] args) {
BigDecimal principal = new BigDecimal("100000");
BigDecimal annualRate = new BigDecimal("12");
System.out.println("Min EMI for 12 months: " + findMinEmi(principal, annualRate, 12));
}
}
Min EMI for 12 months: 8884.88
Visual Overview
Array: [1001, 1025, 1050, 1100, 1200, 1350, 1500]
Target: 1200
Step 1: low=0 high=6 mid=3 arr[3]=1100 < 1200 → low=4
[1001, 1025, 1050, 1100, 1200, 1350, 1500]
^^^ low────────high
Step 2: low=4 high=6 mid=5 arr[5]=1350 > 1200 → high=4
[1001, 1025, 1050, 1100, 1200, 1350, 1500]
low──high ^^^
Step 3: low=4 high=4 mid=4 arr[4]=1200 == 1200 → FOUND at index 4
[1001, 1025, 1050, 1100, 1200, 1350, 1500]
^^^
Window halving:
┌───────────────────────────────────────┐
│ n = 1,000,000 │
│ log2(1,000,000) ≈ 20 comparisons │
│ │
│ Step 1: 1,000,000 → 500,000 │
│ Step 2: 500,000 → 250,000 │
│ Step 3: 250,000 → 125,000 │
│ ... │
│ Step 20: 2 → 1 │
└───────────────────────────────────────┘
Key Takeaway
Binary search is the fundamental logarithmic-time algorithm for finding a target in a sorted array. You keep two bounds, low and high, that frame the current search window, and on each step you look at the middle element. If it equals the target you are done. If the middle is smaller than the target, the answer can only be to the right, so you move low past the middle. If the middle is larger, the answer can only be to the left, so you move high below the middle. Every comparison discards half the remaining range, so searching a million elements takes only about twenty steps.
Two implementation details separate a correct solution from a buggy one. First, compute the midpoint as low + (high - low) / 2 rather than (low + high) / 2, because the naive form can overflow a 32-bit integer when the array is very large. Second, always exclude the middle from the next window using +1 and -1, and loop while low <= high so that a single-element window is still checked. Getting these details wrong causes either infinite loops or missed elements.
In Rajesh's work at the National Bank of India, binary search powers the account authentication system. When a customer logs in, the system looks up their account number in a sorted array of millions of active accounts. Binary search confirms the account exists in about 20 comparisons, which meets the strict latency requirements that a linear scan never could.
The deeper reason binary search matters is that it generalizes well beyond arrays. The same halving idea applies to searching on an answer space for optimization problems: finding the minimum EMI that pays off a loan, the minimum capacity to ship packages, or the smallest rate that satisfies a constraint. Mastering the classic version, including the overflow-safe midpoint and the correct loop invariant, pays off far beyond simple array lookups.
Remember one sentence: binary search halves the search window on each step, finding any target in a sorted array of n elements in at most log2(n) comparisons.
---