1、前言
之所以断更了一天,就是因为上次说的这个二分查找,,,看的我心态多没了,之后就这阶段就一直刷二分查找了!!!
这是一个很经典的题目,【二分查找】问题。
初步上手二分查找的时候,总觉得很简单,但是真的简单嘛???
其实并不简单!!!
可以看看一些大佬关于二分查找法的论述:
看到了吧,基本上十人九错,,,
什么是二分查找?
二分查找是计算机科学中最基本、最有用的算法之一。它描述了在有序集合中搜索特定值的过程。
二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。
二分查找中使用的术语:
Target
—— 你要查找的值;Index
—— 你要查找的当前位置;Left
,Right
—— 我们用来维持查找空间的指标;Mid
—— 我们用来应用条件来确定我们应该向左查找还是向右查找的索引;代码大体都没啥问题,就是边界条件,比方说:while
的不等号是否应该带等号,right
和 left
是不是要让 mid
加一等等。
2、代码
模板:
// Cint 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探索之后,再讲下一篇。