二分查找（折半查找）

一、算法解释

二分查找也常被称为二分法或者折半查找，每次查找时通过将待查找区间分成两部分并只取一部分继续查找，将查找的复杂度大大减少。对于一个长度为 O(n) 的数组，二分查找的时间复 杂度为 O(log n)。

举例来说，给定一个排好序的数组 {3, 4, 5, 6, 7}，我们希望查找 4 在不在这个数组内。第一次折半时考虑中位数 5，因为 5 大于 4 ，所以如果 4 存在于这个数组，那么其必定存在于 5 左边这一 半。于是我们的查找区间变成了 {3, 4, 5}。(注意，根据具体情况和您的刷题习惯，这里的 5 可以保留也可以不保留，并不影响时间复杂度的级别)。第二次折半时考虑新的中位数 4，正好是我们需要查找的数字。于是我们发现，对于一个长度为 5 的数组，我们只进行了 2 次查找。如果是遍历数组，最坏的情况则需要查找 5 次。

我们也可以用更加数学的方式定义二分查找。给定一个在 [a, b] 区间内的单调函数 f(x)，若 f(a) 和 f(b) 正负性相反，那么必定存在一个解 c，使得f(c) = 0。在上个例子中，f(x) 是离散函数 f(x) = x + 2，查找 4 是否存在等价于求 f(x) - 4 = 0 是否有离散解。因为 f(1) - 4 = 3 - 4 = -1 < 0，f(5) - 4 = 7 - 4 = 3 > 0，且函数在区间内单调递增，因此我们可以利用二分查找求解。如果最后二分到了不能再分的情况，如只剩一个数字，且剩余区间里不存在满足条件的解，则说明不存在离散解，即 4 不在这个数组内。

具体到代码上，二分查找时区间的左右端取开区间还是闭区间在绝大多数时候都可以，因此有时会容易搞不清楚如何定义区间开闭性。这里提供两个小诀窍，第一是尝试熟练使用一种写法，比如左闭右开（满足编程的习惯）或左闭右闭（便于处理边界条件）， 尽量只保持这一种写法；第二是在刷题时思考如果最后区间只剩下一个数或者两个数，自己的写法是否会陷入死循环，如果某种写法无法跳出死循环，则考虑尝试另一种写法。

二分查找也可以看作双指针的一种特殊情况，但我们一般会将二者区分。双指针类型的题， 指针通常是一步一步移动的，而在二分查找里，指针每次移动半个区间长度。

二、求开方

2.1、x 的平方根

2.1.1、题目描述

69. x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意： 不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

2.1.2、输入输出示例

示例1：
输入： x = 4
输出： 2

示例2：
输入： x = 8
输出： 2
解释： 8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

2.1.3、题解

二分查找的下界为 0，上界可以粗略地设定为 x。在二分查找的每一步中，我们只需要比较中间元素 mid 的平方与 x 的大小关系，并通过比较的结果调整上下界的范围。

class Solution {
    
    public int mySqrt(int x) {
    
        int left = 0, right = x, ans = -1;
        while (left <= right) {
    
            int mid = left + (right - left) / 2;
            if ((long) mid * mid <= x) {
    
                ans = mid;
                left = mid + 1;
            } else {
    
                right = mid - 1;
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(logx)，即为二分查找需要的次数。
• 空间复杂度：O(1)。

三、查找区间

3.1、在排序数组中查找元素的第一个和最后一个位置

3.1.1、题目描述

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

3.1.2、输入输出示例

示例1：
输入： nums = [5, 7, 7, 8, 8, 10], target = 8
输出： [3,4]

示例2：
输入： nums = [5, 7, 7, 8, 8, 10], target = 6
输出： [-1,-1]

示例3：
输入： nums = [], target = 0
输出： [-1,-1]

3.1.3、题解

四、选择数组查找数字

4.1、搜索旋转排序数组 II

4.1.1、题目描述

81. 搜索旋转排序数组 II

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

4.1.2、输入输出示例

示例1：
输入： nums = [2, 5, 6, 0, 0, 1, 2], target = 0
输出： true

示例2：
输入： nums = [2, 5, 6, 0, 0, 1, 2], target = 3
输出： false

4.1.3、题解

五、练习

5.1、基础难度

5.1.1、寻找旋转排序数组中的最小值 II

5.1.1.1、题目描述

寻找旋转排序数组中的最小值 II

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
• 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
  
  

注意，数组 [a[0], a[1], a[2], ..., a[n-1]]旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须尽可能减少整个过程的操作步骤。

5.1.1.2、输入输出示例

示例1：
输入： nums = [1, 3, 5]
输出： 1

示例1：
输入： nums = [2, 2, 2, 0, 1]
输出： 0

5.1.1.3、题解

5.1.2、有序数组中的单一元素

5.1.2.1、题目描述

有序数组中的单一元素

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

5.1.2.2、输入输出示例

示例1：
输入： nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]
输出： 2

示例1：
输入： nums = [3, 3, 7, 7, 10, 11, 11]
输出： 10

5.1.2.3、题解

5.2、进阶难度

5.2.1、寻找两个正序数组的中位数

5.2.1.1、题目描述

寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

5.2.1.2、输入输出示例

示例1：
输入： nums1 = [1, 3], nums2 = [2]
输出： 2.00000
解释： 合并数组 = [1, 2, 3] ，中位数 2

示例1：
输入： nums1 = [1, 2], nums2 = [3, 4]
输出： 2.50000
解释： 合并数组 = [1, 2, 3, 4] ，中位数 (2 + 3) / 2 = 2.5

5.2.1.3、题解