力扣Hot100——35.搜索插入的位置(二分查找)
除暴力循环,更好的办法是二分查找,降低查询次数。
二分查找思想
如果一个问题,待查找的数是一个整数,且知道范围,大概就可以使用二分查找算法。
- 设置 left 、 right 与mid 分别标示数组的头、尾以及中间位置
- 每次根据 nums[mid] 与 target 之间的大小进行判断,相等直接返回 mid,若 nums[mid] < target 则 left 右移至 mid+1 ;若 nums[mid] > target 则 right 左移至 mid-1
- 查找结束,如果没有相等则返回 left,该值为插入位置下标
- 循环退出条件为 left > right
public int searchInsert(int[] nums, int target) {
// 二分查找法
int left = 0, right = nums.length - 1;
while(left <= right){
int mid = (left + right) >> 1;
if(nums[mid] == target){
return mid;
}
else if(nums[mid] < target){
left = mid + 1;
}
else{
right = mid - 1;
}
}
return left;
}
还有一种修改的方式为,将 nums[mid] == target 的情况与 nums[mid] == target 放在一起处理。这样做,在两数相等的时候会错过一次输出,但是在下一次循环的时候,left一定会大于 right,并且 left 指向的就是 target。也就是多循环了一次,少了一些判断。
public int searchInsert(int[] nums, int target) {
// 二分查找法
int left = 0, right = nums.length - 1;
while(left <= right){
int mid = (left + right) >> 1;
if(nums[mid] < target){
left = mid + 1;
}
else{ //将 nums[mid] < target 放在这里处理
right = mid - 1;
}
}
return left;
}