Definition
- Iterative binary search – finds a target in a sorted array using a loop and two pointers,
leftandright, with no recursive calls. - Halving – each iteration computes the midpoint, compares it to the target, and discards one half of the range.
- Constant space – uses only a few integer variables, so there is no call-stack growth and no risk of stack overflow.
- Template – the standard form uses
while (left <= right)withmid + 1andmid - 1to guarantee termination. - Production choice – Java's
Arrays.binarySearchis iterative internally for these efficiency reasons.
Picture a clerk at the National Bank of India searching a sorted ledger with two bookmarks, one at the first page in range and one at the last. She flips to the page exactly between the bookmarks. If the account she wants is earlier, she moves the right bookmark to just before that page; if it is later, she moves the left bookmark to just after. She keeps flipping to the new middle, tightening the bookmarks, until she lands on the account or the bookmarks cross, meaning it is not there. She never needs a stack of notes, just the two bookmarks.
Understanding the Concepts
What is iterative binary search?
Iterative binary search is the loop-based implementation of the binary search algorithm. Instead of calling itself recursively, it uses a while loop that runs as long as the search range is valid. This makes it the preferred form for production code because it avoids recursion overhead and eliminates the risk of stack overflow on large arrays.
package com.bank.search;
import java.math.BigDecimal;
public class IterativeBinarySearch {
public static int search(BigDecimal[] balances, BigDecimal target) {
int left = 0;
int right = balances.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int cmp = balances[mid].compareTo(target);
if (cmp == 0) {
return mid;
} else if (cmp < 0) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
BigDecimal[] balances = {
new BigDecimal("5000.00"),
new BigDecimal("15000.00"),
new BigDecimal("30000.00"),
new BigDecimal("50000.00"),
new BigDecimal("75000.00")
};
int idx = search(balances, new BigDecimal("30000.00"));
System.out.println("Found at index: " + idx);
}
}
Found at index: 2
Why prefer the iterative form over recursion?
The iterative form uses O(1) extra space. It stores only three integers: left, right, and mid. The recursive version creates a new stack frame for each halving step, consuming O(log n) space and risking a StackOverflowError if the array is extremely large.
In a banking system processing millions of sorted transaction IDs under tight memory constraints, the iterative form is the safe and efficient default.
package com.bank.search;
public class RecursiveVsIterative {
// Recursive version: O(log n) stack space
public static int recursiveSearch(int[] arr, int target, int left, int right) {
if (left > right) return -1;
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) return recursiveSearch(arr, target, mid + 1, right);
return recursiveSearch(arr, target, left, mid - 1);
}
// Iterative version: O(1) space
public static int iterativeSearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
public static void main(String[] args) {
int[] txnIds = {101, 205, 310, 412, 520};
System.out.println("Recursive: " + recursiveSearch(txnIds, 412, 0, txnIds.length - 1));
System.out.println("Iterative: " + iterativeSearch(txnIds, 412));
}
}
Recursive: 3
Iterative: 3
How does the loop template guarantee correctness?
The template while (left <= right) combined with mid + 1 and mid - 1 guarantees three things:
- Every valid single-element range where
left == rightis checked. - The range strictly shrinks on every iteration because
midis always excluded. - The loop always terminates because the range shrinks by at least one each step.
If you use while (left < right) instead, you miss the case where the target is the single remaining element. If you forget the + 1 or - 1, the loop can spin forever.
package com.bank.search;
public class TemplateCorrectness {
// WRONG: left < right misses single-element range
public static int buggy(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left < right) { // BUG
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
// CORRECT: left <= right
public static int correct(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {10, 20, 30};
System.out.println("Buggy search for 30: " + buggy(arr, 30));
System.out.println("Correct search for 30: " + correct(arr, 30));
}
}
Buggy search for 30: -1
Correct search for 30: 2
How do you handle an empty array or a single element?
When the array is empty, left = 0 and right = -1, so left <= right is false and the loop never runs, correctly returning -1. When the array has a single element, left = right = 0, the loop runs once, checks arr[0], and either matches or exits.
package com.bank.search;
public class EdgeCases {
public static int search(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
public static void main(String[] args) {
System.out.println("Empty array: " + search(new int[]{}, 5));
System.out.println("Single match: " + search(new int[]{5}, 5));
System.out.println("Single miss: " + search(new int[]{3}, 5));
}
}
Empty array: -1
Single match: 0
Single miss: -1
How do you adapt the template for lower-bound and upper-bound?
The leftmost-match (lower-bound) variant does not return early on a match. Instead it records the match and continues searching leftward. The rightmost-match (upper-bound) variant continues searching rightward.
package com.bank.search;
public class BoundarySearch {
public static int lowerBound(int[] arr, int target) {
int left = 0, right = arr.length - 1, result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid;
right = mid - 1; // keep searching left
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
public static int upperBound(int[] arr, int target) {
int left = 0, right = arr.length - 1, result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid;
left = mid + 1; // keep searching right
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
public static void main(String[] args) {
int[] amounts = {100, 200, 200, 200, 300, 400};
System.out.println("First 200 at index: " + lowerBound(amounts, 200));
System.out.println("Last 200 at index: " + upperBound(amounts, 200));
}
}
First 200 at index: 1
Last 200 at index: 3
What is the time and space complexity?
| Aspect | Value |
|---|---|
| Time complexity | O(log n) |
| Space complexity | O(1) |
| Best case | O(1) when the middle element is the target |
| Worst case | O(log n) when the target is at an edge or absent |
| Comparisons for n = 1,000,000 | At most 20 |
package com.bank.search;
public class Complexity {
public static void main(String[] args) {
for (int n : new int[]{100, 10_000, 1_000_000}) {
System.out.println("n=" + n + " max comparisons="
+ (int) Math.ceil(Math.log(n) / Math.log(2)));
}
}
}
n=100 max comparisons=7
n=10000 max comparisons=14
n=1000000 max comparisons=20
What are the common mistakes developers make?
The three classic bugs in iterative binary search:
1. Midpoint overflow: using `(left + right) / 2` instead of `left + (right - left) / 2`. 2. Wrong loop condition: using `<` instead of `<=`, which skips single-element ranges. 3. Missing pointer advancement: using `left = mid` instead of `left = mid + 1`, causing an infinite loop.
Each of these can silently produce wrong results or hang the program.
package com.bank.search;
public class InfiniteLoopBug {
// WRONG: left = mid causes infinite loop when left == mid
public static int infiniteLoop(int[] arr, int target) {
int left = 0, right = arr.length - 1;
int iterations = 0;
while (left <= right) {
iterations++;
if (iterations > 100) {
System.out.println("Stuck in infinite loop!");
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid; // BUG: should be mid + 1
else right = mid - 1;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50};
infiniteLoop(arr, 50);
}
}
Stuck in infinite loop!
When should a senior engineer choose iterative over recursive?
A senior engineer uses the iterative form as the default for all standard binary search lookups. The recursive form is reserved for problems where the recursion naturally models the structure, such as binary search tree validation where the bounds are passed to child calls. For the flat-array case, iterative is always preferred because it is constant space, cache-friendly, and has no overhead from function calls.
Java's own Arrays.binarySearch is iterative internally for exactly these reasons.
package com.bank.search;
import java.util.Arrays;
public class ProductionChoice {
public static void main(String[] args) {
long[] sortedAccounts = new long[1_000_000];
for (int i = 0; i < sortedAccounts.length; i++) {
sortedAccounts[i] = 1000L + i;
}
long start = System.nanoTime();
int idx = Arrays.binarySearch(sortedAccounts, 500_500L);
long elapsed = System.nanoTime() - start;
System.out.println("Found at: " + idx);
System.out.println("Time: " + elapsed + " ns");
}
}
Found at: 499500
Time: 1200 ns
Visual Overview
Iterative Binary Search Flow:
┌────────────────────────────────┐
│ left = 0, right = n - 1 │
└──────────────┬─────────────────┘
▼
┌────────────────────────────────┐
│ while (left <= right) │◄─────────┐
└──────────────┬─────────────────┘ │
▼ │
┌────────────────────────────────┐ │
│ mid = left + (right-left)/2 │ │
└──────────────┬─────────────────┘ │
▼ │
┌────────────────┐ │
│ arr[mid]==target│──yes──► return mid │
└───────┬────────┘ │
│ no │
▼ │
┌────────────────┐ │
│arr[mid]<target │──yes──► left=mid+1 ┤
└───────┬────────┘ │
│ no │
▼ │
right = mid - 1 ──────────────────────┘
Loop ends: return -1 (not found)
Key Takeaway
Iterative binary search finds a target in a sorted array using a loop and two pointers, left and right, that bound the active range. On each iteration you compute the midpoint, compare the middle element to the target, and move either the left pointer past the midpoint or the right pointer below it to discard half the range. Because each step halves the range, it runs in O(log n) time, and because it uses only a couple of integer variables, it uses O(1) extra space.
The template must be exact because the boundaries are where bugs hide. The loop runs while left <= right. The midpoint is left + (right - left) / 2 to avoid integer overflow. When you move a pointer you use mid + 1 or mid - 1 to exclude the already-checked middle, which guarantees the range strictly shrinks and the loop always terminates.
In a banking system at the National Bank of India, the iterative form runs on hot paths that confirm whether a specific transaction ID exists in a sorted array, executing millions of times under tight memory limits. The iterative version is constant space with no call-stack growth, so there is zero risk of a stack overflow and the constant factors are tiny and cache-friendly.
The senior-level point is that the iterative form is the default over recursion for plain lookups, and the same skeleton adapts to richer variants. By adjusting when you stop and which direction you keep searching, the identical loop finds the leftmost or rightmost occurrence among duplicates, or a lower or upper bound. Java's own Arrays.binarySearch is iterative internally for exactly these reasons.
Remember one sentence: iterative binary search uses a tight loop with left and right pointers to halve the sorted range each step in constant space.
---