Question
Given a sorted array 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 may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
Stats
| Frequency | 2 |
| Difficulty | 2 |
| Adjusted Difficulty | 2 |
| Time to use | ---------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This is a very basic, yet very difficult question. It is not easy to get it correct at first attempt.
Read this blog for more.
My code
public class Solution {
public int searchInsert(int[] A, int target) {
if (A == null || A.length == 0) {
return 0;
}
int len = A.length;
int left = 0;
int right = len - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (A[mid] >= target) {
right = mid;
} else {
left = mid;
}
}
// now are have a adjacent range [left, right]
if (target <= A[left]) {
return left;
} else if (target <= A[right]) {
// remember not to miss the == case
return right;
} else {
return right + 1;
}
}
}