再也不怕女朋友问我二分查找了!【手绘漫画】图解二分查找(修订版)(LeetCode 704题)

在这里插入图片描述

图解算法与数据结构

1、前言

上次讲到的更的二分查找模板在很多地方让我使用起来不是特别的舒服,感谢B站上的y大佬,让我找到了一个新的模板!!!
在这里插入图片描述
下面一起来看看吧!!!
在这里插入图片描述
本次的模板应对重复元素也可以~
在这里插入图片描述
在这里插入图片描述

2、代码

模板一:

// C
int lower_bound(int* nums, int numsSize, int target){
	int left = 0;
	int right = numsSize-1;
	while(left < right){	// 搜索区间[first, last)不为空
		// 防溢出
		int mid = left + right >> 1;
		if(nums[mid] >= target) right = mid;
		else left = mid + 1;
	}
	return left;			// right也行,因为[left, right)为空的时候它们重合
}

首先一定要明确,数组是升序的!!!

如果中点大于等于 target,表示目标在左侧,数组范围应该从 [left, right] 变成 [left, mid],否则,就从 [left, right] 变成 [mid+1, right]

为什么 right 不加一?

因为是大于等于,带着等于,也就是 mid 有可能是我们的解!!!
在这里插入图片描述


模板二:

// C
int lower_bound(int* nums, int numsSize, int target){
	int left = 0;
	int right = numsSize-1;
	while(left < right){	// 搜索区间[first, last)不为空
		// 防溢出
		int mid = left + right + 1 >> 1; // 防止死循环,mid加1
		if(nums[mid] <= target) left = mid;
		else right = mid + 1;
	}
	return left;			// right也行,因为[left, right)为空的时候它们重合
}

首先一定要明确,数组是升序的!!!

如果中点小于等于 target,表示目标在右侧,数组范围应该从 [left, right] 变成 [mid, right],否则,就从 [left, right] 变成 [left, mid+1]

为什么 left 不加一?

因为是小于等于,带着等于,也就是 mid 有可能是我们的解!!!
在这里插入图片描述

  • 模板一:区间 [left, right] 划分成 [left, mid][mid + 1, right] 时,其更新操作是 right = mid 或者 left = mid + 1;,计算 mid 时不需要加 1
  • 模板二:区间 [left, right] 划分成 [left, mid - 1][mid, right] 时,其更新操作是 r = mid - 1 或者 l = mid;,此时为了防止死循环,计算 mid 时需要加 1

在这里插入图片描述

3、实例(LeetCode 704题)

首先看一下题目,
在这里插入图片描述
代码:

int search(int* nums, int numsSize, int target){
    int left=0;
    int right=numsSize-1;
    while(left<right){
        int mid=left+right >> 1;
        if(nums[mid]>=target){
            right=mid;
        }
        else{
            left=mid+1;
        }
    }
    if(nums[left]==target) return left;
    return -1;
}

在这里插入图片描述
作为最经典的二分查找题,这个题依旧复合我们的模板,没错就是 模板一!!!

唯一不同的是,要注意判断结果,不能只写个 left ,因为是存在 -1 的情况的,加个 if(nums[left]==target) return left; 就好了。

这里自然又更容易的方法,但是 练习模板,万法接通,每日一遍,养成习惯!!!
在这里插入图片描述
附上最经典的二分查找解法:

// C
int search(int* nums, int numsSize, int target){
    int left = 0;
    int right = numsSize - 1;

    while (left <= right) {
    	// 最好这么写,不然会内存溢出
    	// 同时还能减少运行时间!!!
        int mid = (left + right) >> 1;
        // 等于的情况最简单,首先判断,没准一下就中了!
        if (nums[mid] == target) {
            return mid;
        }
        else if (nums[mid] < target) {
            // 左边界更新为 mid + 1
            left = mid + 1;
        }
        else {
            // 右边界更新为 mid - 1
            right = mid - 1;
        }
    }
    return -1;
}

在这里插入图片描述
在这里插入图片描述

如果有幸帮到你,请帮我点个【赞】,给个【关注】!如果能顺带【评论】给个鼓励,我将不胜感激。

如果想要更多的资源,欢迎关注 @我是管小亮,文字强迫症MAX~

再也女朋友二分查找了!!!【手绘漫画】面试必考之二分查找(解模板和深度剖析),最终回
文章目录1、前言2、万恶之源3、二分查找LeetCode 704)4、x 的平方根(LeetCode 69)5、猜数字大小(LeetCode 374)6、搜索旋转排序数组(LeetCode 33)7、讨论 1、前言 今天是二分查找的最后一更,来做一下LeetCode中的探索的~ 【手绘漫画】面试必考之二分查找(解模板和深度剖析),上回 【手绘漫画】面试必考之二分查找(解模板和深度剖析)...
实现简单的文件系统
01-26
实验内容: 通过对具体的文件存储空间的管理、文件的物理结构、目录结构和文件操作的实现,加深对文件系统内部功能和实现过程的理解。 要求: 1.在内存中开辟一个虚拟磁盘空间作为文件存储器,在其上实现一个简
【记录】一个深度学习算法工程师的成长之路(思考和方法以及计划)
文章目录0、写在前面1、编程能力 0、写在前面 讲道理,一谈到【找工作】这个,我就很焦虑。。。。。。看到这个省略号了嘛?这就是我的心, ???? 尤其是在就业一年比一年难的情况下,经历过好多次心态崩裂,也过很多人,来总结一下如果想成为一个【深度学习 CV 算法工程师】需要什么学习能力和知识储备。 这个文章应该会是一个【记录】的文章,看看自己这一路走来 学了什么,准备学什么,需要学什么,希望和各位共...
用C++写二分查找了!【手绘漫画图解LeetCode之搜索插入位置(LeetCode 35)
文章目录图解LeetCode计划1、写在前面2、目3、正文4、代码 图解LeetCode计划 1、写在前面 手绘漫画系列正式上线!!!“图解LeetCode计划” 来了!!! 今天是第十五期,争取每天一期,最多两天一期,欢迎大家监督我。。。 最近依旧是二分查找算法呢~ 使用新版的模板加上图解,相信你能更加理解二分法的使用!!! 2、目 首先看一下目, 分界条件就是出现错误...
手绘漫画图解LeetCode之搜索旋转排序数组(LeetCode33),二分查找
文章目录图解LeetCode计划1、写在前面2、目3、正文4、代码5、讨论 图解LeetCode计划 1、写在前面 手绘漫画系列正式上线!!!“图解LeetCode计划” 来了!!! 今天是第六期,争取每天一期,最多两天一期,欢迎大家监督我。。。 目前的目暂定 一两个月必定开启剑指offer,敬请期待。 今日依旧还是是二分查找算法~ 2、目 首先看一下目, 排序,旋转...
??2020 CSDN 皮肤主题: 酷酷鲨 设计师:CSDN官方博客 返回首页