二分查找

一、算法解释

????????二分查找也常被称为二分法或者折半查找，每次查找时通过将待查找区间分成两部分并只取一部分继续查找，将查找的复杂度大大减少。对于一个长度为 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 不在这个数组内。

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

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

? ? ? ? 二分查找思路还是很简单的，但是需要注意很多细节东西，否则可能因为一个等号、一个加一减一，就会出现错误，还需要仔细体会理解。

二、经典问题?

1. 求开方

69. x 的平方根

69. Sqrt(x)

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

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

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

????????我们可以把这道题想象成，给定一个非负整数 a ，求 f ( x ) = x 2 ? a = 0 的解。因为我们只考虑 x ≥ 0 ，所以 f ( x ) 在定义域上是单调递增的。考虑到 f ( 0 ) = ? a ≤ 0 ， f ( a ) = a 2 ? a ≥ 0 ，我们可以对 [ 0 , a ] 区间使用二分法找到 f ( x ) = 0 的解。

????????在以下的代码里，为了防止除以 0 ，我们把 a = 0 的情况单独考虑，然后对区间 [ 1 , a ] 进行二分查找。我们使用了左闭右闭的写法。

????????注意： mid = ( l + r )/ 2 可能会因为 l + r 溢出而错误，因而采用 mid = l + ( r ? l )/ 2 的写法。

class Solution {
public:
    int mySqrt(int x) {
        if(x == 0)  return x;
        int l = 1,r = x,mid,sqrt;
        while(l <= r){
            mid = l + (r - l)/2;
            sqrt = x / mid;
            if(mid == sqrt){
                return mid;
            }else if(mid > sqrt){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return r;
    }
};

????????另外，这道题还有一种更快的算法——牛顿迭代法，其公式为 x n + 1 = x n ? f ( x n )/ f ′ ( x n ) 。给定 f ( x) = x 2 ? a = 0，这里的迭代公式为 xn+ 1 = (x n + a / x n )/ 2 ，其代码如下。

???????? 注意：这里为了防止 int 超上界，我们使用 long 来存储乘法结果。

int mySqrt(int a) {
    long x = a;
    while (x * x > a) {
        x = (x + a / x) / 2;
    }
    return x;
}

2. 查找区间

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

34. Find First and Last Position of Element in Sorted Array

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

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

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

????????这道题可以看作是自己实现 C++ 里的 lower_bound 和 upper_bound 函数。这里我们尝试使用左闭右开的写法，当然左闭右闭也可以。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.empty()){
            return vector<int>{-1,-1};
        }
        int lower = lower_bound(nums,target);
        int upper = upper_bound(nums,target) - 1; // 注意减1位
        if(lower == nums.size() || nums[lower] != target){
            return vector<int>{-1,-1};
        }
        return vector<int>{lower,upper};
    }
    int lower_bound(vector<int>& nums,int target){
        int l = 0,r = nums.size(),mid;
        while(l < r){
            mid = l + (r - l)/2;
            if(nums[mid] >= target){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
    int upper_bound(vector<int>& nums,int target){
        int l = 0,r = nums.size(),mid;
        while(l < r){
            mid = l + (r - l)/2;
            if(nums[mid] > target){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
};

3. 旋转数组查找数字

81. 搜索旋转排序数组 II

81. Search in Rotated Sorted Array 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 。

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

????????即使数组被旋转过，我们仍然可以利用这个数组的递增性，使用二分查找。对于当前的中点，如果它指向的值小于等于右端，那么说明右区间是排好序的；反之，那么说明左区间是排好序的。如果目标值位于排好序的区间内，我们可以对这个区间继续二分查找；反之，我们对于另一半区间继续二分查找。

????????注意，因为数组存在重复数字，如果中点和左端的数字相同，我们并不能确定是左区间全部相同，还是右区间完全相同。在这种情况下，我们可以简单地将左端点右移一位，然后继续进行二分查找。

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int l = 0,r = nums.size()-1,mid;
        while(l <= r){
            int mid = l + (r - l)/2;
            if(nums[mid] == target){
                return true;
            }
            if(nums[l] == nums[mid]){
                // 无法判断哪个区间是增序的
                ++l;
            }else if(nums[mid] <= nums[r]){
                // 右区间是增序的
                if(target > nums[mid] && target <= nums[r]){
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }
            }else{
                // 左区间是增序的
                if(target >= nums[l] && target < nums[mid]){
                    r = mid - 1;
                }else{
                    l = mid + 1;
                }
            }
        }
        return false;
    }
};

三、巩固练习

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

154. Find Minimum in Rotated Sorted Array 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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

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

????????旋转排序数组 nums 可以被拆分为 2 个排序数组 nums1 , nums2 ，并且 nums1任一元素 >= nums2任一元素；因此，考虑二分法寻找此两数组的分界点 nums[i]n (即第 2 个数组的首个元素)。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0,r = nums.size()-1,mid;
        while(l < r){
            mid = l + (r - l)/2;
            if(nums[mid] == nums[r]){
                --r;
            }else if(nums[mid] > nums[r]){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        return nums[l];
    }
};

540. 有序数组中的单一元素

540. Single Element in a Sorted Array

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

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

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

????????由于给定数组有序且常规元素总是两两出现，因此如果不考虑“特殊”的单一元素的话，我们有结论：成对元素中的第一个所对应的下标必然是偶数，成对元素中的第二个所对应的下标必然是奇数。

????????然后再考虑存在单一元素的情况，假如单一元素所在的下标为 x，那么下标 x 之前（左边）的位置仍满足上述结论，而下标 x 之后（右边）的位置由于 x?的插入，导致结论翻转。

存在这样的二段性，指导我们根据当前二分点 mid 的奇偶性进行分情况讨论：

????????mid 为偶数下标：根据上述结论，正常情况下偶数下标的值会与下一值相同，因此如果满足该条件，可以确保 mid 之前并没有插入单一元素。正常情况下，此时应该更新 l = mid，否则应当让 r = mid - 1，但需要注意这样的更新逻辑，会因为更新 r 时否决 mid 而错过答案，我们可以将否决 mid 的动作放到更新 l 的一侧，即需要将更新逻辑修改为 l = mid + 1 和 r = mid；

????????mid 为奇数下标：同理，根据上述结论，正常情况下奇数下标的值会与上一值相同，因此如果满足该条件，可以确保 mid 之前并没有插入单一元素，相应的更新 l 和 r。

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int n = nums.size();
        int l = 0,r = n - 1,mid;;
        while(l < r){
            mid = l + (r - l)/2;
            if(mid % 2 == 0){
                if(mid + 1 < n && nums[mid] == nums[mid + 1])
                    l = mid + 1;
                else    
                    r = mid;
            }else{
                if(mid - 1 >= 0 && nums[mid - 1] == nums[mid])
                    l = mid + 1;
                else    
                    r = mid; 
            }
        }
        return nums[r];
    }
};

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

4. Median of Two Sorted Arrays

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

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