Search Insert Position
Given a sorted array of distinct integers and a target, return the index of the target if it is in the array. If it is not, return the index where it would be inserted to keep the array sorted. The solution must run in O(log n). This is LeetCode 35.
Example 1
Output: 2
Example 2
Output: 1
Example 3
Output: 4
How to Think About It
Step 1: Both answers are the same question
If the target is present, its index is the first position holding a value that is at least the target. If it is absent, it would be inserted in front of the first larger value, which is again the first position holding a value at least the target. So both cases ask for one thing: the first index where nums[i] >= target
Step 2: That position is a boundary
For [1, 3, 5, 6]nums[i] >= 2
Step 3: The answer can be past the end
For target 7 every test is false, and the answer is 4, the length of the array. So the search range is [0, n][0, n - 1]hi = nums.length
Step 4: Never throw away a possible answer
- If
, mid is too small, and so is everything before it:nums[mid] < target .lo = mid + 1 - Otherwise
might be the answer, so keep it:mid , nothi = mid .mid - 1 - Stop when
: only one candidate is left, and it is the answer.lo == hi
Walkthrough
Target 2 in [1, 3, 5, 6]
| lo | hi | mid | nums[mid] | Decision |
|---|---|---|---|---|
| 0 | 4 | 2 | 5 | 5 >= 2: could be the answer, hi = 2 |
| 0 | 2 | 1 | 3 | 3 >= 2: hi = 1 |
| 0 | 1 | 0 | 1 | 1 < 2: lo = 1 |
| 1 | 1 | lo == hi: answer 1 |
Java Solution
The loop uses lo < hihi = midlo <= hihi = midlo == hi
public class SearchInsertPosition {
// Returns the first index whose value is >= target (the "lower bound")
public static int searchInsert(int[] nums, int target) {
int lo = 0;
int hi = nums.length; // the answer can be nums.length: insert at the end
while (lo < hi) { // stop when lo == hi: one candidate left
int mid = lo + (hi - lo) / 2;
if (nums[mid] < target) {
lo = mid + 1; // mid is too small, so the answer is after it
} else {
hi = mid; // mid could be the answer, keep it in the range
}
}
return lo;
}
public static void main(String[] args) {
int[] nums = {1, 3, 5, 6};
System.out.println(searchInsert(nums, 5)); // 2
System.out.println(searchInsert(nums, 2)); // 1
System.out.println(searchInsert(nums, 7)); // 4
System.out.println(searchInsert(nums, 0)); // 0
}
}
The original implementation, std::lower_boundArrays.binarySearch-(insertion point) - 1
Complexity
- Time: O(log n).
- Space: O(1).
The same lower-bound search finds both ends of a run of equal values in