Search for a command to run...
What it teaches: The lower-bound template: the first index whose value is at least the target.
Practise it on judges as “Search Insert Position”.
Given a sorted array of distinct integers and a target, return the index if found, or the index where it would be inserted to keep the order.
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
Pattern clues in the wording
These clues point to Binary Search on an Index: In sorted data, check the middle and throw away the half that can't contain the answer.
Stuck? Take one hint at a time
class Solution {
public int searchInsert(int[] nums, int target) {
return 0;
}
}Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
Test cases
| # | Input | Expected |
|---|---|---|
| 1 | nums = [1,3,5,6] target = 5 | 2 |
| 2 | nums = [1,3,5,6] target = 2 | 1 |
| 3 | nums = [1,3,5,6] target = 7 | 4 |
+ 1 hidden test the code runner will check
From slow to fast
lo = 0, hi = n; while lo < hi: if nums[mid] >= target, hi = mid; else lo = mid + 1. Return lo.
class Solution {
public int searchInsert(int[] nums, int target) {
int lo = 0, hi = nums.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] >= target) hi = mid;
else lo = mid + 1;
}
return lo;
}
}Verdict: One template, no special cases.
Before you submit
Test these inputs
Mistakes people make
Interview
What does Java's Arrays.binarySearch return when the key is missing?