一、题目
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
二、解答
2.1 方法一：顺序查找
public int searchInsert(int[] nums, int target) {
for(int i = 0; i < nums.length; i++){
if (nums[i] >= target){
return i;
}
}
return nums.length;
}
2.2 方法二：二分查找
public int searchInsert(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
while (l <= r){
int mid = (l+r)/2;
if (target == nums[mid]){
return mid;
}else if (target >nums[mid]){
l = mid + 1;
}else {
r = mid - 1;
}
}
2.3 方法三：二分查找优化+模版
2.3.1 优化点
int mid = (l+r)/2; 其中l+r可能产生溢出
- 优化方案一：int mid = l + (r - l) / 2 ;能减少溢出的概率，但不能避免。
- 完美方案：int mid = (left + right) >>> 1 ;
循环可以进行的条件写成 while (left <= right) 时，在退出循环的时候，需要考虑返回 left 还是 right。
- 本例子中的思考
// 对于 [1,3,5,6]，target = 2，返回大于等于 target 的第 1 个数的索引，此时应该返回 1
// 在上面的 while (left <= right) 退出循环以后，right < left，right = 0 ，left = 1
// 根据题意应该返回 left，
// 如果题目要求你返回小于等于 target 的所有数里最大的那个索引值，应该返回 right
- 优化方案：首先把循环可以进行的条件写成 while(left < right)，在退出循环的时候，一定有 left == right 成立，此时返回 left 或者 right 都可以。
2.3.2 模版
public int searchInsert(int[] nums, int target) {
int len = nums.length;
if (len == 0) {
return 0;
}
int left = 0;
int right = len;
while (left < right) {
int mid = (left + right) >>> 1;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
针对本例优化代码为
public int searchInsert(int[] nums, int target) {
int len = nums.length;
if (len == 0) {
return -1;
}
if (nums[len - 1] < target) {
return len;
}
int left = 0;
int right = len - 1;
while (left < right) {
int mid = (left + right) >>> 1;
if (nums[mid] < target) {
// nums[mid] 的值可以舍弃
left = mid + 1;
} else {
// nums[mid] 不能舍弃
right = mid;
}
}
return right;
}
