图解算法与数据结构
1、🚀前言
之所以断更了一天,就是因为上次说的这个二分查找,,,看的我心态多没了,之后就这阶段就一直刷二分查找了!!!
这是一个很经典的题目,【二分查找】问题。初步上手二分查找的时候,总觉得很简单,但是真的简单嘛???
其实并不简单!!!
可以看看一些大佬关于二分查找法的论述:
算法和程序设计技术的先驱 Donald Ervin Knuth(中文名:高德纳),也就是发明 KMP(Knuth-Morris-Pratt) 算法的那位,是怎么说的:Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky... 这句话我看到的最佳的翻译是:思路很简单,细节是魔鬼。同样是高德纳先生,在其著作《计算机程序设计的艺术 第 3 卷:排序和查找》中指出:二分查找法的思想在 1946 年就被提出来了。但是第 1 个没有 Bug 的二分查找法在 1962 年才出现。
另一位大佬,是《编程珠玑》的作者 Jon Bentley,他是这么说的:When Jon Bentley assigned binary search as a problem in a course for professional programmers, he found that ninety percent failed to provide a correct solution after several hours of working on it, mainly because the incorrect implementations failed to run or returned a wrong answer in rare edge cases.翻译:当 JonBentley 把二分查找作为专业程序员课程中的一个问题时,他发现百分之九十的人在花了几个小时的时间研究之后,没有提供正确的解决方案,主要是因为错误的实现无法正确运行,或者是不能很好地判断边界条件。
看到了吧,基本上十人九错,,,
什么是二分查找?
二分查找是计算机科学中最基本、最有用的算法之一。 它描述了在有序集合中搜索特定值的过程。
二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。
二分查找中使用的术语:
- 目标
Target
—— 你要查找的值; - 索引
Index
—— 你要查找的当前位置; - 左、右指示符
Left
,Right
—— 我们用来维持查找空间的指标; - 中间指示符
Mid
—— 我们用来应用条件来确定我们应该向左查找还是向右查找的索引;
代码大体都没啥问题,就是边界条件,比方说:while
的不等号是否应该带等号,right
和 left
是不是要让 mid
加一等等。
2、🚀代码
模板:
// C
int search(int* nums, int numsSize, int target) {
// 数组一般是升序的,如果最后一个元素小于target,则找不到
// if (nums[numsSize - 1] < target) {
// return -1;
// }
int left = 0;
int right = numsSize - 1;
while (left <= right) {
// int mid = (left + right) / 2;
// int mid = left + (right - left) / 2;
// 最好这么写,不然会内存溢出
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;
}
3、🚀正文
什么时候使用二分查找?
其实如果题目告诉你 排序数组,其实就是在【疯狂暗示】你用二分查找。
那么有哪些地方需要注意呢?- 为什么
while
循环的条件中是<=
,而不是<
?
初始化 right
的赋值是 nums.length - 1
,相当于区间 [left, right]
,
什么时候停止搜索呢?
当然,找到了 target
时终止,或者 while
条件不符时:
找到时:
if(nums[mid] == target)
return mid;
但如果没找到:
就需要 while
循环终止,while(left <= right)
的终止条件是 left == right + 1
。
- 中位数怎么写?
其实很多同学是这么写的,int mid = (left + right) / 2
,这行代码其实是有问题的,在 left
和 right
都比较大的时候,left + right
两个 int
很有可能超过 int
类型的最大值,即整型溢出。
为了避免这个问题,又出现了第二种写法:int mid = left + (right - left) / 2
,事实上,这种写法在 right
很大、 left
是负数且很小的时候,right - left
也有可能超过 int
类型能表示的最大值,只不过溢出的可能性很小。
更好的写法是:int mid = (left + right) >> 1
。
但是这种写法存在局限,等我完成LeetCode探索之后,再讲下一篇。
4、🚀实例
- 【手绘漫画】图解LeetCode之寻找旋转排序数组中的最小值(LeetCode153题)
- 【手绘漫画】图解LeetCode之寻找旋转排序数组中的最小值 II(LeetCode154题)
- 【手绘漫画】图解LeetCode之寻找重复数(LeetCode287题),抽屉原理
- 【手绘漫画】图解LeetCode之最长上升子序列(LeetCode300题),贪心算法 + 二分查找
- 【手绘漫画】图解LeetCode之搜索旋转排序数组(LeetCode33题),二分查找
如果有幸帮到你,请帮我点个【赞】,给个【关注】!如果能顺带【评论】给个鼓励,我将不胜感激。
如果想要更多的资源,欢迎关注 @我是管小亮,文字强迫症MAX~