Comment on page

35.Search-Insert-Position

35. Search Insert Position

题目地址

题目描述

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.
​
Example
[1,3,5,6], 5 → 2
​
[1,3,5,6], 2 → 1
​
[1,3,5,6], 7 → 4
​
[1,3,5,6], 0 → 0
​
Challenge
O(log(n)) time

代码

Appraoch 1: Find the first position
public class Solution {
public int searchInsert(int[] A, int target) {
if (A == null | A.length == 0) return 0;
​
int start = 0;
int end = A.length - 1;
​
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mind] == target) {
return mid;
} else if (A[mid] < target) {
start = mid;
} else {
end = mid;
}
}
​
if (A[start] >= target) {
return start;
} else if (A[end] >= target) {
return end;
} else {
return end + 1;
}
​
/// approach 2:
if (target < A[0]) return 0;
​
if (A[end] == target) return end;
if (A[start] == target) return start;
if (A[end] < target) return end + 1;
​
return start + 1;
​
}
​
}