Leetcode 刷题笔记-Leetcode 101 第4章 二分查找

Leetcode 刷题笔记-Leetcode 101 第4章 二分查找

二分查找

二分查找也常被称为二分法或者折半查找，每次查找时通过将待查找区间分成两部分并只取一部分继续查找，将查找的复杂度大大减少。

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

一点点细节小笔记

1. 最基本的二分查找算法：

因为我们初始化 right = nums.length - 1，所以决定了我们的「搜索区间」是 [left, right]，所以决定了 while (left <= right)，同时也决定了 left = mid+1 和 right = mid-1，因为我们只需找到一个 target 的索引即可，所以当 nums[mid] == target 时可以立即返回。

2. 寻找左侧边界的二分查找：

因为我们初始化 right = nums.length，所以决定了我们的「搜索区间」是 [left, right)，所以决定了 while (left < right)，同时也决定了 left = mid + 1 和 right = mid，因为我们需找到 target 的最左侧索引，所以当 nums[mid] == target 时不要立即返回，而要收紧右侧边界以锁定左侧边界。

3. 寻找右侧边界的二分查找：

因为我们初始化 right = nums.length，所以决定了我们的「搜索区间」是 [left, right)，所以决定了 while (left < right)，同时也决定了 left = mid + 1 和 right = mid，因为我们需找到 target 的最右侧索引，所以当 nums[mid] == target 时不要立即返回，而要收紧左侧边界以锁定右侧边界，又因为收紧左侧边界时必须 left = mid + 1，所以最后无论返回 left 还是 right，必须减一。

求开方

Leetcode 69

给定一个非负整数，求它的开方，向下取整。

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

思路很简单，主要是细节问题，已经整理了笔记。

查找区间

Leetcode 34

给定一个增序的整数数组和一个值，查找该值第一次和最后一次出现的位置。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> result;
        int n = nums.size();
        if (n == 0){
            return vector<int>{-1, -1};
        }
        int left = 0;
        int right = n;
        while(left < right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] >= target){
                right = mid;
            }
            else if(nums[mid] < target){
                left = mid + 1;
            }
        }
        if(right >= n || nums[right] != target){
            return vector<int>{-1, -1};
        }
        else{
            result.push_back(right);
        }
        left = 0;
        right = n;
        while(left < right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] > target){
                right = mid;
            }
            else if(nums[mid] <= target){
                left = mid + 1;
            }
        }
        result.push_back(left - 1);
        return result;
    }
};

分析：也是最基础的二分查找，实现了 upper_bound和 lower_bound两个函数。

错误：判断的时候忘记判断是否越界。

旋转数组查找数字

Leetcode 81

一个原本增序的数组被首尾相连后按某个位置断开（如[1,2,2,3,4,5] - [2,3,4,5,1,2]，在第一位和第二位断开），我们称其为旋转数组。给定一个值，判断这个值是否存在于这个旋转数组中。

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n;
        while(left < right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] == target){
                return true;
            }
            else if(nums[mid] < nums[right-1]){
                // 说明右端是排好序的
                if(target >= nums[mid] && target <= nums[right-1]){
                    left = mid + 1;
                }
                else{
                    right = mid;
                }
            }
            else if(nums[mid] > nums[right-1]){
                // 说明左端是排好序的
                if(target <= nums[mid] && target >= nums[left]){
                    right = mid;
                }
                else{
                    left = mid + 1;
                }
            }
            else{
                --right;
            }
        }
        return false;
    }
};

分析：旋转数组是一类经典题目，需要抓住旋转后二分会有一个区间是单调的性质进行判断，从而对所查找的数字进行区间的锁定。

错误：条件考虑不全面，没有对旋转数组充分理解。

练习

Leetcode 154

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

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int left = 0;
        int right = n;
        int minnum = 10000;
        while(left < right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] > nums[left]){
                // 左边一定有序
                minnum = min(minnum,nums[left]);
                left = mid + 1;
            }
            else if(nums[mid] < nums[left]){
                // 右边一定有序
                minnum = min(minnum,nums[mid]);
                right = mid;
            }
            else{
                minnum = min(minnum,nums[mid]);
                ++left;
            }
        }
        return minnum;
    }
};

分析：比查找还要稍稍简单一点，只需要想好最小值可能出现的位置即可。

错误：相等的时候没有判断，会导致漏掉元素。

Leetcode 540

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

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

分析：如果mid是偶数，则比较nums[mid]和nums[mid+1]是否相等；如果mid是奇数，则比较nums[mid−1]和nums[mid]是否相等。

错误：感觉需要判断很多条件？其实不用，只需要考虑长度为1的数组，然后根据下标寻找规律就可以。

Leetcode 4

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

分析：二分的解法太难了。。后续补充吧

错误：没有思路。。。

总结

二分查找是非常好的降低时间复杂度的方法之一，整体的思想不是很难，但是细节的部分需要多多注意。当然也有难题，还要多练习。