LintCode 60. Search Insert Position 原创Java参考解答
问题描述
http://www.lintcode.com/en/problem/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
解题思路
- 先检查数组nums是否为null或者为空数组，若是则直接返回0。
- 用二分法在数组中查找target值的位置。若查到了，直接返回该target位置。如果没有查到，则比较二分法查找后最后剩下两个位置的数与target值的大小关系。放在相应位置即可。
参考代码
public class Solution {
/**
* param A : an integer sorted array
* param target : an integer to be inserted
* return : an integer
*/
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[mid] == target) {
return mid;
} else if (A[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (A[end] < target) {
return end + 1;
} else if (A[start] < target) {
return end;
} else {
return start;
}
}
}