题目要求是：给定一个数组，数组里面都是按升序拍好的数字，并且无重复数字；另外给一个比较的数字target，查找这个target在数组中是否出现，如果出现，返回出现的位置；如果没出现，返回应该“插入”的位置。
分析：这个问题其实就是对target与数组中的数字进行比较，如果采用暴利的方法，按顺序挨个查找，效率上不太好；因为这个数组是有顺序排列好的（升序），想到了一个快速查找的方法，二分查找。
二分查找的思想是：本质上是一种分治的策略，给定一个low指定最前端的位置，一个high指定最后端的位置，一个mid指定中间位置。每次进行比较时，比较mid位置上的值与target的大小，若target<nums【mid】，说明target一定在low到mid-1的位置中间，那么就把mid-1 赋给high；若target>nums【 mid】，target一定在mid+1 到high的位置中间，把mid+1赋给low；若target=num【mid】，此时的target的位置找到，返回位置……如此递归，直到low>high，结束递归。
以上是考虑的数组中有target的情况，那如果没有target怎么办呢？
模拟了三种情况：
1.target在数组的最左边。
nums=1,2,5,7,11，target=-4
当low>high时，此时的low恰好为target新插入的位置。
2.target在数组的最右边。
nums=1,2,5,7,11，target=888
当low>high时，此时的low恰好为target新插入的位置。
3.target在数组的中间。
nums=1,2,5,7,11，target=4
当low>high时，此时的low恰好为target新插入的位置。
那么算法就可以写成如下。
public class Solution {
public int searchInsert(int[] nums, int target) {
int low,high;
low = 0;
high = nums.length - 1;
return binSearch(nums,low,high,target);
}
public int binSearch(int[] nums, int low, int high, int target){
while(low <= high){
int mid = (low + high)/2;
if(target < nums[mid]) return binSearch(nums, low, mid - 1, target);
else if(target > nums[mid]) return binSearch(nums, mid + 1, high, target);
else return mid;
}
return low;
}
}
网友评论