Binary Search is the most important search algorithm in all of DSA. Not because LC #704 is hard — it's Easy — but because the binary search pattern appears everywhere: in rotated arrays, in 2D matrices, in invisible search spaces (Koko Eating Bananas, Find Peak Element), and in almost every hard array/sorting problem.
If your binary search has ever had an off-by-one bug — infinite loop, skipping the target, or returning the wrong boundary — this guide will fix it permanently. We'll break down the exact mechanics of every boundary decision, show you why lo + (hi - lo) // 2 instead of (lo + hi) // 2, trace through every case fully, and map out the 6 variants that show up in actual interviews.
lo <= hi and Not lo < hiLeetCode #704 — Binary Search
Given an array of integers nums sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, return its index. Otherwise, return -1.
Constraints: 1 <= nums.length <= 10^4, all values in nums are unique, nums is sorted in ascending order.
Input: nums = [-1, 0, 3, 5, 9, 12], target = 9 → Output: 4
Input: nums = [-1, 0, 3, 5, 9, 12], target = 2 → Output: -1
Input: nums = [5], target = 5 → Output: 0
Input: nums = [5], target = -5 → Output: -1The key property that makes binary search possible is that the array is sorted. This gives us a superpower: at every step, by looking at just the middle element, we can determine which half of the array the target cannot be in — and discard that entire half.
Linear search checks every element: O(n) comparisons for n elements. Binary search halves the remaining elements at every step:
n = 1,000,000 elements
Linear search (worst case): 1,000,000 comparisons
Binary search (worst case): log₂(1,000,000) ≈ 20 comparisons
After each step:
Step 1: 1,000,000 elements → 500,000
Step 2: 500,000 → 250,000
Step 3: 250,000 → 125,000
...
Step 20: 2 → 1This is why binary search is one of the most powerful tools in DSA — it reduces a million-element problem to 20 comparisons. The catch: the array must be sorted (or have some monotonic property you can exploit).
The midpoint formula seems trivial but has a real-world bug hiding in it:
# ❌ Naive formula — works in Python, but dangerous in Java/C++
mid = (lo + hi) // 2
# ✅ Safe formula — works in all languages
mid = lo + (hi - lo) // 2
# In Java/C++, if lo = 1,000,000,000 and hi = 1,500,000,000:
# lo + hi = 2,500,000,000 → OVERFLOW (exceeds 32-bit int max of ~2.1 billion)
# lo + (hi - lo) = 1,000,000,000 + 500,000,000 = 1,500,000,000 ✅ safePython integers have arbitrary precision so overflow doesn't apply there — but in Java and C++, using (lo + hi) / 2 when both values are large 32-bit integers causes integer overflow, producing a negative midpoint and completely wrong behavior. Always use lo + (hi - lo) / 2 as a habit regardless of language.
In Java, you'll sometimes see mid = (lo + hi) >>> 1 (unsigned right shift). This avoids overflow too, but lo + (hi - lo) / 2 is clearer and works identically. Use whichever your team prefers, but always be able to explain why the naive formula can overflow.
At each iteration, we compute mid and compare nums[mid] to target. There are exactly three cases:
nums[mid] == target — Found it. Return mid.nums[mid] < target — The target is to the right of mid. We can safely discard everything from lo to mid (inclusive). Set lo = mid + 1.nums[mid] > target — The target is to the left of mid. We can safely discard everything from mid to hi (inclusive). Set hi = mid - 1.lo = mid + 1 and hi = mid - 1 (not mid)?We already checked nums[mid] and it wasn't the target. So mid itself is no longer a candidate. If we set lo = mid or hi = mid, we'd re-examine the same index on the next iteration — which with a 1-element or 2-element search space causes an infinite loop. The +1 and -1 guarantee we always make progress.
lo <= hi and Not lo < hiThis is the most common source of off-by-one bugs in binary search. The loop condition should be while lo <= hi. Here's why:
Consider a 1-element array: nums = [5], target = 5. We start with lo = 0, hi = 0. The only element is at index 0. If our loop condition were lo < hi, the condition 0 < 0 is immediately false — we'd never enter the loop and return -1 incorrectly. With lo <= hi, 0 <= 0 is true, we enter the loop, check nums[0] == 5, and correctly return 0.
nums = [5], target = 5
lo = 0, hi = 0
With "while lo < hi": 0 < 0 → FALSE → skip loop → return -1 ❌
With "while lo <= hi": 0 <= 0 → TRUE → enter loop → check nums[0]=5=target → return 0 ✅The loop terminates naturally when lo > hi — which happens when the search space is completely exhausted (every element has been considered and ruled out). At that point, the target genuinely doesn't exist in the array, and we return -1.
Indices: 0 1 2 3 4 5
Values: [-1, 0, 3, 5, 9, 12]
Initial: lo = 0, hi = 5
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 1:
lo=0, hi=5 → lo <= hi ✅ → enter loop
mid = 0 + (5-0)//2 = 2
nums[2] = 3
3 < 9 → target is to the right
lo = mid + 1 = 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 2:
lo=3, hi=5 → 3 <= 5 ✅ → enter loop
mid = 3 + (5-3)//2 = 4
nums[4] = 9
9 == 9 → FOUND!
return 4 ✅
Total comparisons: 2 (out of 6 elements)Initial: lo = 0, hi = 5
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 1:
mid = 0 + (5-0)//2 = 2
nums[2] = 3
3 > 2 → target is to the left
hi = mid - 1 = 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 2:
lo=0, hi=1 → 0 <= 1 ✅
mid = 0 + (1-0)//2 = 0
nums[0] = -1
-1 < 2 → target is to the right
lo = mid + 1 = 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 3:
lo=1, hi=1 → 1 <= 1 ✅
mid = 1 + (1-1)//2 = 1
nums[1] = 0
0 < 2 → target is to the right
lo = mid + 1 = 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Check: lo=2, hi=1 → 2 <= 1 ✗ → exit loop
return -1 ✅
Target 2 does not exist in the array.def search(nums: list[int], target: int) -> int:
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2 # overflow-safe mid
if nums[mid] == target:
return mid # found: return index
elif nums[mid] < target:
lo = mid + 1 # target is to the right — discard left half
else:
hi = mid - 1 # target is to the left — discard right half
return -1 # search space exhausted: target not in arrayclass Solution {
public int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // overflow-safe
if (nums[mid] == target) {
return mid; // found
} else if (nums[mid] < target) {
lo = mid + 1; // discard left half
} else {
hi = mid - 1; // discard right half
}
}
return -1; // not found
}
}var search = function(nums, target) {
let lo = 0, hi = nums.length - 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2); // overflow-safe
if (nums[mid] === target) {
return mid; // found
} else if (nums[mid] < target) {
lo = mid + 1; // discard left half
} else {
hi = mid - 1; // discard right half
}
}
return -1; // not found
};The recursive approach passes lo and hi as parameters instead of maintaining them as variables. It's functionally identical to the iterative version but uses the call stack to track state.
Base cases:
lo > hi — search space is exhausted, target not found → return -1nums[mid] == target — found → return midRecursive cases:
nums[mid] < target → recurse on right half: search(nums, target, mid+1, hi)nums[mid] > target → recurse on left half: search(nums, target, lo, mid-1)The recursive solution has O(log n) space complexity due to the call stack — the same number of frames as iterations in the iterative version. For very large arrays (n = 10^7+), prefer iterative to avoid stack overflow risk.
def search(nums: list[int], target: int) -> int:
def binary_search(lo: int, hi: int) -> int:
# Base case: search space exhausted
if lo > hi:
return -1
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid # found
elif nums[mid] < target:
return binary_search(mid + 1, hi) # search right half
else:
return binary_search(lo, mid - 1) # search left half
return binary_search(0, len(nums) - 1)class Solution {
public int search(int[] nums, int target) {
return binarySearch(nums, target, 0, nums.length - 1);
}
private int binarySearch(int[] nums, int target, int lo, int hi) {
if (lo > hi) return -1; // base case: not found
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) return binarySearch(nums, target, mid + 1, hi);
else return binarySearch(nums, target, lo, mid - 1);
}
}var search = function(nums, target) {
function binarySearch(lo, hi) {
if (lo > hi) return -1; // base case: not found
const mid = lo + Math.floor((hi - lo) / 2);
if (nums[mid] === target) return mid;
else if (nums[mid] < target) return binarySearch(mid + 1, hi);
else return binarySearch(lo, mid - 1);
}
return binarySearch(0, nums.length - 1);
};lo < hi Instead of lo <= hiCauses the algorithm to miss a 1-element search space. When lo == hi, there's still one element to check. lo < hi skips it and incorrectly returns -1.
Fix: Always use while lo <= hi.
lo = mid or hi = mid Instead of mid ± 1When nums[mid] != target, mid is already ruled out. Setting lo = mid keeps mid in the search space. When lo and hi are adjacent (e.g., lo=4, hi=5, mid=4), this sets lo = 4 again — an infinite loop that never terminates.
Fix: Always use lo = mid + 1 and hi = mid - 1.
hi = len(nums) Instead of len(nums) - 1Initializing hi = len(nums) means hi starts out-of-bounds. If mid ever equals len(nums) - 1 when hi is len(nums), it still works by coincidence — but it breaks the loop invariant and can cause index-out-of-bounds in variant problems where you access nums[hi] directly.
Fix: Always initialize hi = len(nums) - 1.
(lo + hi) // 2 in Java/C++When both lo and hi are near Integer.MAX_VALUE, their sum overflows a 32-bit integer and becomes negative, producing a completely wrong mid.
Fix: Always use lo + (hi - lo) / 2.
| Approach | Time | Space | Notes |
|---|---|---|---|
| Iterative | O(log n) | O(1) | Halves search space each iteration. Only 3 integer variables regardless of array size. |
| Recursive | O(log n) | O(log n) | Each recursive call adds a stack frame. log₂(10^4) ≈ 14 frames max for given constraints. |
For the given constraints (nums.length <= 10^4), both approaches are perfectly fine. In production with extremely large datasets, iterative is strictly preferred due to O(1) space.
LC #704 tests binary search in its simplest form. Real interview problems almost always use a variant. Here are the six most common, in order of increasing difficulty:
| Problem | The Twist | Key Change to Template | Difficulty |
|---|---|---|---|
| LC #35 — Search Insert Position | Target may not exist; find where it would be inserted | Return lo (not -1) when loop ends — lo is always the insertion point | Easy |
| LC #34 — Find First and Last Position | Array has duplicates; find leftmost AND rightmost occurrence | Two separate binary searches: one biases left (hi = mid), one biases right (lo = mid) | Medium |
| LC #33 — Search in Rotated Sorted Array | Array is sorted but rotated at some pivot | Determine which half is sorted, then check if target falls in it; search that half | Medium |
| LC #153 — Find Minimum in Rotated Sorted Array | No explicit target; find the pivot/minimum | Compare nums[mid] to nums[hi] to determine which side has the minimum | Medium |
| LC #162 — Find Peak Element | Array has no target; find any local maximum | Compare nums[mid] to nums[mid+1]; move toward the higher neighbor | Medium |
| LC #875 — Koko Eating Bananas | Search space is the answer value, not array indices | Binary search on the answer range [1, max(piles)]; check feasibility with a helper | Medium |
Binary search doesn't require a sorted array — it requires a monotonic condition. Anywhere you can say "if X is true at index i, it's true for all indices beyond i" (or before i), binary search applies. Koko Eating Bananas (LC #875) has no sorted array at all — the search space is the eating rate itself, and the condition "can finish in h hours at rate k?" is monotonically true for all k above some threshold.
This template adapts to every binary search variant by changing only the condition inside the loop:
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1 # ← adjust search space for variant problems
while lo <= hi:
mid = lo + (hi - lo) // 2
if CONDITION(mid): # ← this is the only thing that changes per problem
return mid
elif MOVE_RIGHT(mid): # ← target is to the right
lo = mid + 1
else: # ← target is to the left
hi = mid - 1
return -1 # ← sometimes return lo for insertion-point variants
# LC #704: CONDITION = nums[mid]==target, MOVE_RIGHT = nums[mid]lo <= hi — handles 1-element arrays correctlylo + (hi - lo) // 2 — overflow-safe alwayslo = mid + 1 — mid is already checked, skip ithi = mid - 1 — mid is already checked, skip itlo at the end instead of -1.Tag on DSAPrep.dev under Array and Binary Search.