Boundary update without `+1` / `-1`
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.
A complete visual walkthrough of binary search — finding a target or where it belongs in a sorted array.
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [1,3,5,6], target = 5 Output: 2
Example 2:
Input: nums = [1,3,5,6], target = 2 Output: 1
Example 3:
Input: nums = [1,3,5,6], target = 7 Output: 4
Constraints:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums contains distinct values sorted in ascending order.-104 <= target <= 104The simplest approach: scan left to right until you find the target or the first element greater than the target. That index is your answer.
Array: [1, 3, 5, 6], target = 5
Array: [1, 3, 5, 6], target = 2
This works, but it's O(n) — we check every element in the worst case. Since the array is sorted, we can do much better.
// Brute force: O(n) for (int i = 0; i < nums.length; i++) { if (nums[i] >= target) return i; } return nums.length;
// Brute force: O(n) for i, v := range nums { if v >= target { return i } } return len(nums)
# Brute force: O(n) for i in range(len(nums)): if nums[i] >= target: return i return len(nums)
// Brute force: O(n) for (i, &v) in nums.iter().enumerate() { if v >= target { return i as i32; } } nums.len() as i32
// Brute force: O(n) for (let i = 0; i < nums.length; i++) { if (nums[i] >= target) return i; } return nums.length;
lo Is the AnswerStandard binary search narrows a range [lo, hi] until lo > hi. The beautiful insight for this problem:
When the loop ends without finding the target, lo always points to the correct insertion position. Here's why:
When lo crosses hi, lo sits right where the target would be inserted — all elements before lo are smaller, all elements from lo onward are larger.
This is the standard binary search template! The only difference from a "find element" binary search is: instead of returning -1 when not found, we return lo. That single change solves the entire problem.
Let's trace through with nums = [1, 3, 5, 6], target = 2 (insert case):
lo=0, hi=3, mid=1
nums[1] = 3 > target (2) → target is to the left → hi = mid - 1 = 0
lo=0, hi=0, mid=0
nums[0] = 1 < target (2) → target is to the right → lo = mid + 1 = 1
Return lo = 1 — insert 2 at index 1, between 1 and 3. The array becomes [1, 2, 3, 5, 6].
Binary search handles these naturally — no special code needed:
class Solution { public int searchInsert(int[] nums, int target) { int lo = 0, hi = nums.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // avoids integer overflow if (nums[mid] == target) { return mid; // found it! } else if (nums[mid] < target) { lo = mid + 1; // search right half } else { hi = mid - 1; // search left half } } return lo; // not found — lo is the insert position } }
func searchInsert(nums []int, target int) int { lo, hi := 0, len(nums)-1 for lo <= hi { mid := lo + (hi-lo)/2 // avoids integer overflow if nums[mid] == target { return mid // found it! } else if nums[mid] < target { lo = mid + 1 // search right half } else { hi = mid - 1 // search left half } } return lo // not found — lo is the insert position }
class Solution: def search_insert(self, nums: list[int], target: int) -> int: lo, hi = 0, len(nums) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 # avoids integer overflow if nums[mid] == target: return mid # found it! elif nums[mid] < target: lo = mid + 1 # search right half else: hi = mid - 1 # search left half return lo # not found — lo is the insert position
impl Solution { pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 { let (mut lo, mut hi) = (0i32, nums.len() as i32 - 1); while lo <= hi { let mid = lo + (hi - lo) / 2; // avoids integer overflow if nums[mid as usize] == target { return mid; // found it! } else if nums[mid as usize] < target { lo = mid + 1; // search right half } else { hi = mid - 1; // search left half } } lo // not found — lo is the insert position } }
function searchInsert(nums: number[], target: number): number { let lo = 0, hi = nums.length - 1; while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); if (nums[mid] === target) { return mid; // found it! } else if (nums[mid] < target) { lo = mid + 1; // search right half } else { hi = mid - 1; // search left half } } return lo; // not found — lo is the insert position }
Why lo + (hi - lo) / 2 instead of (lo + hi) / 2? When lo and hi are both large, their sum can overflow a 32-bit integer. The subtraction form avoids this. Functionally identical, but safer.
Try different arrays and targets. Step through each binary search iteration to see lo, hi, and mid move.
Each iteration halves the search space. For an array of length n, we perform at most log2(n) comparisons. We use only a few integer variables -- no extra data structures, giving O(1) space.
A single for-loop scans left to right, returning the first index where nums[i] >= target. If the target is larger than every element, the loop exhausts all n entries before returning n. Only one loop variable is needed.
Standard binary search halves the search range each iteration: compare nums[mid] with the target, move lo or hi accordingly. After at most log2(n) iterations lo lands on the correct index -- either the target itself or the insert position. Only three integer variables (lo, hi, mid) are used.
The lo pointer ends at the insertion point when the element is absent. For n = 1,000,000 elements, binary search takes at most 20 comparisons (since 220 ≈ 1M). The brute force would need up to 1,000,000 comparisons. That is the power of logarithmic time.
Review these before coding to avoid predictable interview regressions.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.