#35
Search Insert Position
Easy Lower bound
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
In a sorted array of distinct values, return the index of target, or the index where it would be inserted to keep the order.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: where is target, or where would it go?
Why this works: when the search fails, lo ends at the first value bigger than target, which is the insert spot.
Example: [1, 3, 5, 6], target 2
mid 1 (3) > 2 → hi 0mid 0 (1) < 2 → lo 1answer 1
✦Hints open one at a time
You want the first index whose value is >= target.
That's the "lower bound". When the loop ends, lo points to it.
↗Approach
Binary search with lo, hi = 0, n − 1. When the loop ends without a hit, lo is exactly the insert position.
</>Solution (Java)
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;
if (nums[mid] == target) return mid;
if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return lo; // first index with value > target
}
}!Common mistake
Returning hi or mid at the end — it's lo.
Complexity
- Time: O(log n).
- Space: O(1).
Topic: Binary Search
🎬 Episodes 21–23: video coming soon