视频讲解：《算法不好玩》二分查找专题 (opens new window) （已经录制的部分，能够帮助大家完全搞懂二分查找算法，非常适合初学的朋友们）。
# 第 1 节 二分查找的基本思想
友情提示：
- 所有的「二分查找」都只有一个逻辑：逐渐缩小搜索区间 （减而治之）。二分查找没有难到解决不了，无从下手。虽然网上提供了很多二分查找的「模板」，但是 写算法问题不是背模板，并往里面填空；
- 如果你对什么时候设置
right = len还是right = len - 1，向左边走还是向右边走不清楚，这些需要从题目中得出，不看题目凭空想是没有用的；- 出现死循环的时候，把
left、mid和right的值看一下就清楚了。
个人经历：
- 在我还没有系统学习《算法与数据结构》的时候，我就知道这个算法。但那个时候，只是作为一个练习，写了一个二分查找算法，自己造了一个数据，运行一下就算完；
- 二分查找法的写法有比较多种。我在「力扣」上做题的过程中，也进行了学习和总结；
- 学会「二分查找」的最好方法就是不断做题和练习，一旦掌握了，就不会觉得「二分查找」很难了，这个过程会很爽。
二分查找是一个思想很简单的算法。
# 生活中的二分查找
幸运 52 猜价格游戏，主持人说高了，观众就猜一个更低的价格，主持人说低了，观众就猜一个更高的价格。观众猜价格用的就是「二分查找」的思想，即：逐渐缩小搜索区间，学术化的叫法是：减而治之（Decrease and Conquer）。
# 可以使用「二分查找」的前提
可以使用「二分查找」的前提是：问题告诉我们的 单调性。
有些问题虽然没有指出单调性，但是可以从题目中的描述得到可以 逐步缩小搜索区间 的条件，这些问题也可以使用「二分查找」来解决。
# 学习「二分查找」的最基本问题
我最早认识的二分查找算法是：在一个有序数组里查找一个数，如果找到就返回这个数在有序数组里的下标，找不到就返回
这个问题在「力扣」上是第 704 题：二分查找 (opens new window)。
# 例：「力扣」第 704 题：二分查找（简单）
# 题目描述
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1：
输入: nums = [-1, 0, 3, 5, 9, 12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2：
输入: nums = [-1, 0, 3, 5, 9, 12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：
- 你可以假设
nums中的所有元素是不重复的。 n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。
# 解题思路
基本想法：在循环中做判断，每一轮通过目标元素与中间元素的大小将搜索区间分为 3 个部分。根据看到的中间元素的数值，想清楚下一次搜索的区间是什么，进而设置
left或者right的值。
# 具体做法
- 先看中间的数与目标元素的关系，如果等于目标元素，就直接返回中间的数的索引；
- 如果中间的数比目标元素大，那么中间位置右边的数也一定比目标元素大，即中间位置右边的数也一定不是目标元素，目标元素只可能在中间位置的左边出现，因此把右边界设置为
mid - 1，即right = mid - 1；（同理看待另一边） - 如果中间的数比目标元素小，那么中间位置左边的数也一定比目标元素小，即中间位置左边的数也一定不是目标元素，目标元素只可能在中间位置的右边出现，因此把左边界设置为
mid + 1，即left = mid + 1。
参考代码 1：循环写法
public class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
if (len == 0) {
return -1;
}
// 在 [left..right] 区间里查找 target
int left = 0;
int right = len - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
// 下一轮搜索区间：[left..mid - 1]
right = mid - 1;
} else {
// 此时 nums[mid] < target
// 下一轮搜索区间：[mid + 1..right]
left = mid + 1;
}
}
// 走到这里，就可以判定输入数组里不存在目标元素，返回 -1
return -1;
}
}
说明：在 while 里面要写 left <= right ，这是因为当 left == right 成立的时候，搜索区间里仍然有一个数，就是 nums[left] 还没有看，因此这个思路的二分查找算法要写等于号。
复杂度分析：
- 时间复杂度：
，这里 是数组的元素个数，每次排除当前候选区间一半以上的元素，因此是对数级别的时间复杂度； - 空间复杂度：
，只使用了常数个的临时变量。
参考代码 2：递归写法
提示：递归写法仅供参考，实际做题的过程中几乎不会用递归实现二分查找。
public class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
if (len == 0) {
return -1;
}
return binarySearch(nums, target, 0, len - 1);
}
/**
* 在数组 arr 的子区间 [left..right] 里搜索目标元素
*
* @param arr 数组
* @param target 目标元素
* @param left 左边界下标，包括 left
* @param right 右边界下标，包括 right
* @return
*/
private static int binarySearch(int[] arr, int target, int left, int right) {
// 先处理递归到底的情况
if (left > right) {
// 不能形成区间，返回 -1 表示没有找到
return -1;
}
int mid = (left + right) / 2;
if (target == arr[mid]) {
// 找到了，就将目标元素的索引返回
return mid;
} else if (target < arr[mid]) {
// 既然是有序数组，目标元素的值比中间元素还要小，就应该在中间元素的左边去找
return binarySearch(arr, target, left, mid - 1);
} else {
// 既然是有序数组，目标元素的值比中间元素还要大，就应该在中间元素的右边去找
return binarySearch(arr, target, mid + 1, right);
}
}
}
复杂度分析：
- 时间复杂度：
，这里 是数组的元素个数，每次排除当前候选区间一半以上的元素，因此是对数级别的时间复杂度； - 空间复杂度：
，这里用到了「递归」，递归需要借助「栈」，「栈」的高度为 。
# 总结
「力扣」第 704 题是最简单的「二分查找」问题，求解这道问题的方法，根据看到的中间位置 mid 的值 nums[mid]，把待搜索区间分成三个部分：
mid位置左边的所有元素；mid位置所在的元素；mid位置右边的所有元素。
重点：
- 编码的思想是：问题的答案只会在三个部分的其中一个部分，所以
while (left <= right)里面有三个循环分支；- 循环可以继续的条件是
left <= right，表示当left和right重合的时候，仍然继续查找。
作者：liweiwei1419 链接：https://suanfa8.com/binary-search 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。