算法专题--数组二分查找--Leetcode704题

储备知识

学习本算法需要掌握：while-else if -else语句，二分法，循环语句

重难点

边界处理（到底是边界还是边界+-1？到底是大于小于还是大于等于、小于等于？）

题目704

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target ，如果目标值存在返回下标，否则返回 -1 。

题目解读

以上题目的意思就是说，现在有一个数组，要求你找出目标值，返回目标值的下标，此题数组二分查找的方法。

我们首先把最左边的元素叫left，最右边的叫做right。最中间的元素叫middle。

那么我们有一下两种二分查找的写法

注意：一个字一个字看，边看边想，不要走神

1.左闭右闭法

顾名思义，我们在区间【left,right】中搜寻目标值target。我们可以认为[left,right]这个升序数组的区间是左闭右闭的。至于两端都是闭区间意味着什么，请你看下去就会理解。

我们使用“二分查找法”。这种方法的核心就是不断的二分来逼近目标值，就像高中所学的求函数交点的二分法一样。不过在数组中，我们相当于是在数轴上离散的点进行操作而已。

我们先对得到的这个区间求中间值，然后拿中间值和目标值比较。这时出现3种情况：

1.最中间的一个数的值 = 目标值。此时就找到了目标值。

2.如果位于数组中间的值 > 目标值，说明目标值在左侧区间；

3.如果中间值 < 目标值，说明目标值在右侧区间；

此时再对目标值所在的区间再次进行二分，再次判断它在哪个区间。不断重复上述操作，直到中间值等于目标值，此时我们就可以获得这个中间值的下标。返回该下标就解决了这个问题。

那么我们可以大概写一下这个函数的结构

当左边界left小于等于右边界right时 while(left<right){

//Q1：为什么是小于等于？详情见下文蓝字部分

中间下标middle=（左下标left+右下标right）/2

if（中间下标对应的数值nums[middle] < 目标值target）{

//说明目标值在右侧区间，此时把左下标更新为中间值，不去理会左半部分和中间值

left=middle-1// Q2:为什么要 -1？

else if（nums[middle] > target）

right=middle-1//Q2

else return middle;//中间值等于目标值直接返回中间的下标

}

return -1

//没找到目标值返回-1，题目要求的

}

解释Q1Q2

Q1：为什么是小于等于？

因为我们的区间是左闭右闭的，拿数学来解释，假设有一个数x属于区间【a，b】那么 可以得到 a<=x<=b，这个区间里面x=a=b是完全合法的。方括号闭区间就代表等于和包含。

我们在程序中为了严谨，在左闭右闭的大前提下，当然要用<=确保我们每一个数都参与了运算。

如果你还是一头雾水。那么我们反过来说，如果在上面的while条件中不用=，那么当left==right的时候程序就不会继续执行这下面的判断条件if语句，我们就无法知道这最后一个数(left=right=middle)是否和目标值target相等。

Q2：为什么要+/-1？

我们在程序中if的判断条件是“>”和“<”，else middle=target则直接返回下标

这就意味着前两个大于小于语句中的middle已经判断过是和target不相等的了，所以我们在下一轮的判断中就不需要第一轮的middle参与了，所以直接+/-1从下一个开始算起

左闭右闭法代码展示

class Solution { public: int search(vector<int>& nums, int target) { int left=0; int right=nums.size()-1 ; //计算机里下标都是从0记起的，数组长度-1才是下标 //换种说法我们要求的是左闭右闭，所以right一定得是个有效下标 while(left<=right){ int middle=left+(right-left)/2; //防止溢出，超大数字直接相加除2可能超过INT_MAX（如32位最多只能存2^32，超出会变负数） if(nums[middle]<target){ left=middle+1; // 注意区分+/-1，防止边界反而扩大导致超时 } else if(nums[middle]>target){ right=middle-1; // 注意区分+/-1，防止边界反而扩大导致超时 } else{ return middle; } } return -1; //注意不能在while里面 } };

代码要点

1.int middle=left+(right-left)/2;

在计算中间下标时，通常写作：

int middle = (left + right) / 2;

但这样在left和right都很大时（比如接近INT_MAX，即 2147483647），left + right可能超过 int 能表示的最大值，造成整数溢出。溢出后结果会变成负数（或未定义值），用它做下标访问数组必然越界，程序可能崩溃或出现奇怪行为。

例如，假设left = 2000000000,right = 2000000000，那么left+right = 4000000000，超过INT_MAX，在 32 位 int 中实际会变成4000000000 - 2^32 ≈ -294967296，除以 2 得到负数，显然不是正确的中间位置。

所以求差值得长度是最保险的方法。

2.左闭右开法

左闭右开的条件下，我们参考上面Q1的思路就可以很明显的知道，在 while 句中，就不能再使用"="了，就和数学上的定义一样，假设x是在区间 [a,b) 中的一个数，那么可得a<=x<b，显然a/b两个端点/边界是不存在相等的可能性的。

主体思路一样，我们直接说和上面方法里的不同点。

代码要点/不同点

1.初始化：left = 0,right = nums.size()（因为right是开区间，所以它等于数组长度，就是无效下标，最后一个有效下标是right-1，因为我们要的是左开右闭，就是要让左右不相等）

2.while (left < right)（当left == right时区间为空，无元素可查）

3.边界更新：

• nums[middle] < target⇒left = middle + 1（目标在右边，且 middle 已比较，应排除，新区间为[middle+1, right)）

• nums[middle] > target⇒right = middle（目标在左边，新区间为[left,middle)，注意 middle 本来就不包含在内，这个区间在while那一步就已经决定了）

class Solution { public: int search(vector<int>& nums, int target) { int left = 0, right = nums.size(); // 注意 right 初始为数组长度 while (left < right) { // 区间非空 int middle = left + (right - left) / 2; if (nums[middle] < target) { left = middle + 1; // 目标在右边，移动左边界 } else if (nums[middle] > target) { right = middle; // 目标在左边，移动右边界（开区间） } else { return middle; // 找到 } } return -1; // 未找到 } };