欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 健康 > 美食 > 力扣Hot100——35.搜索插入的位置(二分查找)

力扣Hot100——35.搜索插入的位置(二分查找)

2025/3/17 16:51:23 来源:https://blog.csdn.net/m0_55329111/article/details/146297899  浏览:    关键词:力扣Hot100——35.搜索插入的位置(二分查找)

在这里插入图片描述
除暴力循环,更好的办法是二分查找,降低查询次数。

二分查找思想

如果一个问题,待查找的数是一个整数,且知道范围,大概就可以使用二分查找算法。

  1. 设置 left 、 right 与mid 分别标示数组的头、尾以及中间位置
  2. 每次根据 nums[mid] 与 target 之间的大小进行判断,相等直接返回 mid,若 nums[mid] < target 则 left 右移至 mid+1 ;若 nums[mid] > target 则 right 左移至 mid-1
  3. 查找结束,如果没有相等则返回 left,该值为插入位置下标
  4. 循环退出条件为 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;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词