文章目录
前言一、二分查找二、第一个错误的版本三、搜索插入位置总结前言
Leetcode算法系列:https://leetcode-/study-plan/algorithms/?progress=njjhkd2
简单介绍总结一下二分查找相关的算法题:
一、二分查找
题目链接:https://leetcode-/problems/binary-search/
题目描述:给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
思路:直接采用通用的二分查找算法即可:
class Solution {public int search(int[] nums, int target) {int start=0,end=nums.length-1,mid;while(start<=end){mid=(start+end)/2; // 最好改为:mid = start+(end-start)/2;if(nums[mid]==target)return mid;else if(nums[mid]<target)start=mid+1;elseend=mid-1;}return -1;}}
1,取 mid 值时,采用 mid = start+(end-start)/2; 可以避免当 start 和 end 很大时造成的整数(int)越界。
2,循环结束条件为 start<=end,所以在 while 循环退出时有 start>end,(在此为 start=end+1)。
3,二分查找的时间复杂度为 O(logn),因为每次循环都会将待处理数组的规模缩小一半。
二、第一个错误的版本
题目链接:https://leetcode-/problems/first-bad-version/
题目描述:你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n],你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
思路:保持之间的二分查找框架不变,修改循环退出条件为当前版本正确且上一个版本错误,
public class Solution extends VersionControl {public int firstBadVersion(int n) {if(isBadVersion(1))return 1;int start=2,mid; //区间为[2,n].while(start<=n){//还是按照二分查找的思路来做mid=start+(n-start)/2;if(!isBadVersion(mid)) //缩小区间到[mid+1,n]start=mid+1;else if(!isBadVersion(mid-1)) //如果mid为true,mid-1为false,返回mid即可return mid; else //如果mid-1不是false,缩小区间到[start,mid-1]n=mid-1;}return -1;}}
缺点时要调用两次 isBadVersion函数。
Version2:修改循环判定条件为start<end,在循环退出时的 start 或 end 为我们感兴趣的下标值。并采用合理的缩小规模方式在循环内仅调用一次 isBadVersion 函数。如下:
public class Solution extends VersionControl {public int firstBadVersion(int n) {int start=1,mid;while(start<n){mid=start+(n-start)/2;if(!isBadVersion(mid))start=mid+1;elsen=mid;}return start;}}
上述算法看起来很巧妙,甚至成功的有点侥幸,因为在每次计算 mid 值时,由于向下取整,所以有时候会出现 mid==
start 出现,而不会存在 mid==
n 出现。因此令 n=mid;这样在每次循环时区间规模总会缩小,直至得到最终结果。
在缩小区间时,最好不要采用 start==
mid,很有可能区间不会缩小,陷入死循环。比如当要求找到最后一个正确的版本时会发生这种情况。
三、搜索插入位置
题目链接:https://leetcode-/problems/search-insert-position/
题目描述:给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
思路:采用通用的二分查找框架,如果目标值存在于数组中,由 mid 给出其返回下标;如果不存在的话,由 start 或 end+1 给出返回下标。
class Solution {public int searchInsert(int[] nums, int target) {int start=0,end=nums.length-1,mid;while(start<=end){mid=start+(end-start)/2;if(nums[mid]==target)return mid;else if(nums[mid]<target)start=mid+1;elseend=mid-1;}return start; //关键点在于确定最后一个查找区间和target之间的关系。//return end+1;}}
由 start 或 end+1 给出返回值下标的原因在于:在一个不含目标值的升序数组中采用通用的二分查找算法查找 target 的位置,在循环结束后 end 处的值刚好小于 target;start 处的值刚好大于 target。 比如对于数组 [1,3,4,6,7],查找 5 所在位置:循环结束后 start =3,end = 2。
Version2:修改循环判定条件为start<end,在循环退出时的 start 或 end 为我们感兴趣的下标值。如下:
public int searchInsert(int[] nums, int target) {int end=nums.length-1,start=0,mid;// 特殊判断if (nums[end] < target) return end+1;// 程序走到这里一定有 nums[end] >= target,保证插入位置在区间 [start..end]while(start<end){mid=start+(end-start)/2;if(nums[mid]<target)start=mid+1;// 下一轮搜索的区间是 [mid + 1..end]elseend=mid;// 下一轮搜索的区间是 [start..mid]}return end;}
和 二、查找错误的版本类似:在循环中令 end=mid 来保证循环执行结束。
总结
通用的二分查找判定条件为 start<=end,意味着结果在循环中给出;当采用 start<end 时,结果在循环执行后由 start 或 end 给出。
如果觉得《LeetCode算法题4:二分查找及扩展应用》对你有帮助,请点赞、收藏,并留下你的观点哦!