【手绘漫画】图解LeetCode之第一个错误的版本(LeetCode 278题)
文章目录
图解刷题计划 1、写在前面
手绘漫画系列正式上线!!!“图解刷题计划” 来了!!!
今天是第九期,争取每天一期,最多两天一期,欢迎大家监督我。。。
最近依旧是二分查找算法呢~
使用新版的模板加上图解,相信你能更加理解二分法的使用!!!
2、题目
首先看一下题目,
分界条件就是出现错误!!!调用 API 就可以实现这个功能,简直是白给。
3、正文
首先分析一下情况,(mid)==true 那么说明 mid 出现错误,但是它不一定是第一个,不过目标一定在左侧。
确定一下 left 和 right,然后编写二分查找模板。
可以看到,因为有等号,所以 mid 有可能是第一个错误的地方,所以 right=mid,而另一半情况,因为不带等号,所以 left=mid+1。
4、代码
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);int firstBadVersion(int n) {int left = 0, right = n;while(left < right){int mid = left + (right - left) / 2;if(isBadVersion(mid)) { right = mid; }else { left = mid + 1; }}return left;
}
如果有幸帮到你,请帮我点个【赞】,给个【关注】!如果能顺带【评论】给个鼓励,我将不胜感激。