大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

二分查找

写在前面：

（一）二分法的思想十分容易理解，但是二分法边界处理问题大多数人都是记忆模板，忘记模板后处理边界就一团乱（?:“我懂了”， ✋ :”你懂个?”​）因为我此前也是记忆模板，所以现在想通过一边学习，一边将所学记录成博客教出去（费曼学习法），希望以后能自己推导出边界如何处理，而不仅仅是记忆模板。欢迎一起交流学习，如有看法不一样之处也欢迎留言一起讨论！

（二）我主要解释了二分法的左闭右闭区间，左闭右开区间两种写法，并且每个写法都举了相应的反例，范围写错的话可能会出现的错误等…

1. 简介

故事分享?：

有一天小明到图书馆借了 N 本书，出图书馆的时候，警报响了，于是保安把小明拦下，要检查一下哪本书没有登记出借。小明正准备把每一本书在报警器下过一下，以找出引发警报的书，但是保安露出不屑的眼神：你连二分查找都不会吗？于是保安把书分成两堆，让第一堆过一下报警器，报警器响；于是再把这堆书分成两堆…… 最终，检测了 logN 次之后，保安成功的找到了那本引起警报的书，露出了得意和嘲讽的笑容。于是小明背着剩下的书走了。 从此，图书馆丢了 N – 1 本书。

保安怎么知道只有一本书?没有登记出借，万一全部都没有登记呢​？

这个故事其实说出了二分查找需要的条件

• 用于查找的内容逻辑上来说是需要有序的
• 查找的数量只能是一个，而不是多个

比如在一个有序的数组并且无重复元素的数组中，例如[1, 2, 3, 4, 5, 6]，需要查找3的位置就可以使用二分查找。

在二分查找中，目标元素的查找区间的定义十分重要，不同的区间的定义写法不一样

因为查找的区间是不断迭代的，所以确定查找的范围十分重要，主要就是左右区间的开和闭的问题，开闭不一样，对应的迭代方式也不一样，有以下两种方式：

• 左闭右闭[left, right]

• 左闭右开[left, right)

2. 例子

这是一个使用二分查找的例题

题目如下：

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

示例一：

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例二：

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

• 你可以假设 nums 中的所有元素是不重复的。
• n 将在 [1, 10000]之间。
• nums 的每个元素都将在 [-9999, 9999]之间。

出自704. 二分查找 – 力扣（LeetCode） (leetcode-cn.com)

二分法的思想很简单，因为整个数组是有序的，数组默认是递增的。

• 首先选择数组中间的数字和需要查找的目标值比较
• 如果相等最好，就可以直接返回答案了
• 如果不相等
  • 如果中间的数字大于目标值，则中间数字向右的所有数字都大于目标值，全部排除
  • 如果中间的数字小于目标值，则中间数字向左的所有数字都小于目标值，全部排除

二分法就是按照这种方式进行快速排除查找的

tips:

不用去纠结数组的长度是奇数或者偶数的时候，怎么取长度的一半，以下说明，可以跳过。

当数组的长度为奇数的时候：

是奇数的情况很简单，指向中间的数字很容易理解，如果需要查找的数字为29

因为29大于中间的数字大于11，所以左边的所有数字全部排除

当数组的长度为偶数的时候：

这个时候中间的数字两边的数字数量就不一样了（刚开始学习二分法的时候我经常纠结这个问题，和另外一个长度除2得到的是最中间的数吗的问题，我相信不止我一个人纠结过……但其实这是同一个问题，每次长度除2，如果长度为奇数，得到的中间的数字两边数字数量相同，如果长度为偶数就为上图中间的数字两边的相差为 1）

但是千万不要一直纠结中间的数字两边的数字数量不一样这个问题，因为：

• 两边数量不一样是一定会出现的情况
• 但是这种情况并不影响我们对中间数字和目标数字大小关系的判断
  • 只要中间数字大于目标数字，就排除右边的
  • 只要中间数字小于目标数字，就排除左边的

所以数组长度是偶数还是奇数这个真的不重要，不影响怎么排除的问题，无非是多排除一个数字或者少排除一个数字

• 真正影响的是中间那个数字到底该不该加入下一次的查找中，也就是边界问题

3. 第一种写法（左闭右闭）

二分法最重要的两个点：

• while循环中 left 和 right 的关系，到底是 left <= right 还是 left < right
• 迭代过程中 middle 和 right 的关系，到底是 right = middle – 1 还是 right = middle

3.1 正向写法（正确演示）

第一种写法：每次查找的区间在[left, right]（左闭右闭区间），根据查找区间的定义（左闭右闭区间），就决定了后续的代码应该怎么写才能对。因为定义 target 在[left, right]区间，所以有如下两点：

• 循环条件要使用while(left <= right)，因为当(left == right)这种情况发生的时候，得到的结果是有意义的
• if(nums[middle] > target) ， right 要赋值为 middle – 1， 因为当前的 nums[middle] 一定不是 target ，需要把这个 middle 位置上面的数字丢弃，那么接下来需要查找范围就是[left, middle - 1]

代码如下：

int search(int nums[], int size, int target) //nums是数组，size是数组的大小，target是需要查找的值
{ 
   
    int left = 0;
    int right = size - 1;	// 定义了target在左闭右闭的区间内，[left, right]
    while (left <= right) { 
   	//当left == right时，区间[left, right]仍然有效
        int middle = left + ((right - left) / 2);//等同于 (left + right) / 2，防止溢出
        if (nums[middle] > target) { 
   
            right = middle - 1;	//target在左区间，所以[left, middle - 1]
        } else if (nums[middle] < target) { 
   
            left = middle + 1;	//target在右区间，所以[middle + 1, right]
        } else { 
   	//既不在左边，也不在右边，那就是找到答案了
            return middle;
        }
    }
    //没有找到目标值
    return -1;
}

下面图解算法的实现过程，建议将代码复制到一个文本编辑器中，边看代码边看图。或者我直接准备了图片，保存下来打开看就好了。

首先看一个数组，需要对这个数组进行操作。需要对33进行查找的操作，那么target 的值就是33

• 首先，对 left 的值和 right 的值进行初始化，然后计算 middle 的值
  • left = 0, right = size - 1
  • middle = (left + (right - left) / 2 )

• 比较 nums[middle] 的值和 target 的值大小关系

  • if (nums[middle] > target)，代表middle向右所有的数字大于target
  • if (nums[middle] < target)，代表middle向左所有的数字小于target
  • 既不大于也不小于就是找到了相等的值

• nums[middle] = 13 < target = 33，left = middle + 1

• 见下图：

• 循环条件为 while (left <= right)

• 此时，left = 6 <= right = 11，则继续进行循环

• 当前，middle = left + ((right - left) / 2)，计算出 middle 的值
  

• 计算出 middle 的值后，比较 nums[middle] 和 target 的值，发现：

  • nums[middle] = 33 == target = 33，找到目标

3.2 反向写法(错误演示)

对应第一种正向的写法，我们把循环条件修改看看会发生什么事

• 原查找区间 [left, right]
• 原循环条件是 while (left <= right)

修改后题目对应的条件：

• 查找区间不变，仍然是[left, right]
• 查找数字为27 (target = 27)
• 循环条件修改为while (left < right)

代码：

int search(int nums[], int size, int target) 
{ 
   
    int left = 0;
    int right = size - 1;	
    while (left < right) { 
   	//left <= right 修改为 left < right,其他不变
        int middle = left + ((right - left) / 2);
        if (nums[middle] > target) { 
   
            right = middle - 1;
        } else if (nums[middle] < target) { 
   
            left = middle + 1;
        } else { 
   	
            return middle;
        }
    }
    //没有找到目标值
    return -1;
}

代码图片，边看模拟过程边看代码哦！

好了，现在开始用图片模拟过程

• 初始化一个数组，计算 middle 的值

• 根据计算的 middle 值确定 nums[middle]

• 因为nums[middle] = 13 < target = 27，所以left = middle + 1

• 继续计算 middle 的值

• 因为 nums[middle] = 33 > target = 27，所以 right = middle – 1

• 接着计算 middle 的值

• 因为 nums[middle] = 22 < target = 27，此时 left = middle + 1，此时 left = right，而循环条件为while (left < right)，所以还未找到27 的情况下算法就跳出了循环，返回 -1

4. 第二种写法（左闭右开）

4.1 正向写法（正确演示）

第二种写法：每次查找的区间在 [left, right)，（左闭右开区间）， 根据区间的定义，条件控制应该如下：

• 循环条件使用while (left < right)
• if (nums[middle] > target)， right = middle，因为当前的 nums[middle] 是大于 target 的，不符合条件,不能取到 middle，并且区间的定义是 [left, right)，刚好区间上的定义就取不到 right, 所以 right 赋值为 middle。

代码如下：

int search(int nums[], int size, int target)
{ 
   
	int left = 0;
	int right = size; //定义target在左闭右开的区间里，即[left, right)
	while (left < right) { 
   	//因为left = right的时候，在[left, right)区间上无意义
		int middle = left + ((right - left) / 2);
		if (nums[middle] > target) { 
   
			right = middle; //target 在左区间，在[left, middle)中 
		} else if (nums[middle] < target) { 
   
			left = middle + 1;
		} else { 
   
			return middle;
		}
	} 
    // 没找到就返回-1
	return -1;
}

代码图片：保存下来边看代码边看图片演示过程

• 需要查找的值为3

第一步是初始化 left 和 right 的值，然后计算 middle 的值

• left = 0, right = size
• 循环条件while (left < right)

因为是左闭右开区间，所以数组定义如下：

• 计算 middle 的值，

• 比较 nums[middle] 和 target 的大小：因为 nums[middle] = 22 > target = 3
• 所以 right = middle

• 符合循环的条件，接着计算 middle 的值

• 比较 nums[middle] 和 target 的大小：因为 nums[middle] = 9 > target = 3
• 所以 right = middle

• 符合循环的条件，继续计算 middle 的值

• 比较 nums[middle] 和 target 的大小关系：因为nums[middle] = 0 < target = 3
• 所以 left = middle + 1

• 符合循环条件，接着计算 middle 的值

• 比较 nums[middle] 和 target 的关系：nums[middle] = 3 == target = 3
• 成功找到 target

4.2 反向写法（错误演示）

对应第二种正确的写法，照样把循环条件修改，看会发生什么事

正确的写法中条件为：

• 查找原区间 [left, right)
• 循环条件为 while (left < right)

修改后题目对应的条件：

• 查找区间不变，仍然是 [left, right)

• 循环条件修改为：while (left <= right)

• 查找的数字为26（数组中不存在这个数字！！！）

代码：

int search(int nums[], int size, int target)
{ 
   
	int left = 0;
	int right = size; 
	while (left <= right) { 
   	//条件left < right 修改为 left <= right
		int middle = left + ((right - left) / 2);
		if (nums[middle] > target) { 
   
			right = middle; 
		} else if (nums[middle] < target) { 
   
			left = middle + 1;
		} else { 
   
			return middle;
		}
	} 
    // 没找到就返回-1
	return -1;
}

代码图片：（记得边看边保存图片代码边看图片演示哦！）

以下是演示全过程：

• 同样，开始初始化一个数组

• 先计算 middle 的值

• 判断 nums[middle] 和 target 的大小关系：nums[middle] = 22 < target = 26
• left = middle + 1 （其实这里nums[left] 已经等于27，26不可能找到，接下去就看算法是否能够知道数组中不存在26并且返回-1 了）

• 符合循环条件，计算 middle 的值

• 判断 nums[middle] 和 target 的大小关系：nums[middle] = 57 > target = 26
• right = middle

• 满足循环条件，接着计算 middle 的值

• 比较 nums[middle] 和 target 的大小关系：nums[middle] = 33 > target = 26
• right = middle

• 符合循环条件，继续计算 middle 的值

• 比较 nums[middle] 和 target 大小关系，因为 nums[middle] = 27 > target = 26，
• 所以 right = middle，自此，left 和 right 相遇，但是循环条件被我们修改成 while (left <= right) 会接着做循环

• 接下来就是死循环

• 因为 middle = left + ((right – left) / 2)，当 left = right 的时候，middle 的值不会继续改变

• middle 不继续改变，由于right = middle，right 也不会改变，所以三个数字自此开始不会继续改变

• 循环条件 while (left <= right) 却仍然满足，不会跳出循环

• 死循环……

5. 总结

二分法最重要的两个点，就是循环条件和后续的区间赋值问题

因为两者是相互联系，相互影响的，所以就需要两者统一，如果两者不统一，就会出现问题

所以循环条件和赋值问题必须统一，也就是循环不变量。

相关题目推荐：

• 35.搜索插入位置
• 34. 在排序数组中查找元素的第一个和最后一个位置
• 69. x 的平方根
• 367.有效的完全平方数

本文相关信息:

• 算法学习自微信公众号:“代码随想录”
• 画图软件:Diagrams
• 代码生成图片软件:Carbon

❤️完结撒花❤️