【LeetCode专辑 - 1】二分查找

LeetCode第一弹：二分相关经典题目刷题笔记，这里所有题目都是按照上一篇文章所分享的模板来解题，思路非常清晰

题目列表

• 33. 搜索旋转排序数组
• 34. 在排序数组中查找元素的第一个和最后一个位置
• 69. x-的平方根
• 74. 搜索二维矩阵
• 153. 寻找旋转排序数组中的最小值
• 278. 第一个错误的版本
• 367. 有效的完全平方数
• 540. 有序数组中的单一元素
• 744. 寻找比目标字母大的最小字母
• 852. 山脉数组的峰顶索引

搜索旋转排序数组

• 通过二分找到数组旋转的位置
• 判断要查找的数位于哪一段
• 在段内进行二分查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty())
            return -1;
        // 先找到旋转的位置
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] >= nums[0])
                l = mid;
            else 
                r = mid - 1;
        }
        // 判断位于哪一段
        if (target >= nums[0])
            l = 0;
        else 
            l = r + 1, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target)
                r = mid;
            else 
                l = mid + 1;
        }
        // 这里写nums[l]的话：[1] 0 这个样例会出现问题，没有进入二分，导致 l = r + 1越界
        if (nums[r] == target)
            return l;
        else 
            return -1;
    }
};

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

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

x的平方根

class Solution {
public:
    int mySqrt(int x) {
        if (x <= 1)
            return x;
        int l = 1, r = x;
        while (l < r) {
            // 强行转换成long long类型
            int mid = l + 1ll + r >> 1;
            if (mid <= x / mid)
                l = mid;
            else 
                r = mid - 1;
        }
        return l;
    }
};

搜索二维矩阵

• 一维坐标转二维的形式进行二分查找

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty())
            return false;
        int n = matrix.size(), m = matrix[0].size();
        int l = 0, r = n * m - 1;
        while (l < r) {
            int mid = l + r >> 1;
            // 一维坐标转换成二维坐标
            if (matrix[mid / m][mid % m] >= target)
                r = mid;
            else 
                l = mid + 1;
        }
        return matrix[l / m][l % m] == target;
    }
};

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

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

第一个错误的版本

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (isBadVersion(mid))
                r = mid;
            else
                l = mid + 1;

        }
        return l;
    }
};

有效的完全平方数

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (isBadVersion(mid))
                r = mid;
            else
                l = mid + 1;

        }
        return l;
    }
};

有序数组中的单一元素

• 将两个元素看作一组进行二分，找到边界即为所求

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        // 给数组末尾添加一个数：只需要保证和数组最后一位不相同即可
        nums.push_back(nums.back() + 1);
        int l = 0, r = nums.size() / 2 - 1;
        while (l < r) {
            int mid = l + r >> 1;
            // 边界一定在mid的左边
            if (nums[mid * 2] != nums[mid * 2 + 1])
                r = mid;
            else
                l = mid + 1;
        }
        return nums[r * 2];
    }
};

寻找比目标字母大的最小字母

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        // 二分出第一个大于target的数
        int l = 0, r = letters.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (letters[mid] > target)
                r = mid;
            else
                l = mid + 1;
        }
        // 说明找奥拉恰好大于target的数，返回即可
        if (letters[l] > target)
            return letters[l];
        // 否则返回第一个字符
        return letters[0];
    }
};

山脉数组的峰顶索引

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