复习Day01：数组part01:701. 二分查找、35. 搜索插入位置、367. 有效的完全平方数、69. x的平方根、74. 搜索二维矩阵

之前的blog链接：https://blog.csdn.net/weixin_43303286/article/details/131690654?spm=1001.2014.3001.5501

我用的方法是在leetcode再过一遍例题，明显会的就复制粘贴，之前没写出来就重写，然后从拓展题目中找题目来写。辅以Labuladong的文章看。然后刷题不用CLion了，使用leetcode自带模拟面试环境。

701. 二分查找

直接过，注意边界就好。

相关题目

35.搜索插入位置

leetcode链接：

• 35.搜索插入位置

这里除了需要二分查找，还需要如果target不在数组内，返回待插入的位置。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        int middle = (right - left) / 2 + left;
        int pos = 0;
        while(left <= right){
            middle = (right - left) / 2 + left;
            if(nums[middle] > target){
                right = middle - 1;
            }else if(nums[middle] < target){
                left = middle + 1;
            }else{
                return middle;
            }
        }
        return right + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

367. 有效的完全平方数

• 367.有效的完全平方数(opens new window)

使用二分法，left为1，right为num，找平方根

class Solution {
public:
    bool isPerfectSquare(int num) {
        int left = 1,  right = num;
        while(left <= right){
            int middle = (right - left) / 2 + left;
            if((long)middle * middle < num){
                left = middle + 1;
            }else if((long)middle * middle > num){
                right = middle - 1;
            }else{
                return true;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

69. x的平方根

class Solution {
public:
    int mySqrt(int x) {
        long left = 1, right = x;
        while(left <= right){
            long middle = (right - left) /2 + left;
            if(middle * middle < x){
                left = middle + 1;
            }else if (middle * middle > x){
                right = middle - 1;
            }else{
                return middle;
            }
        }
        return right;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

跟上面那题差不多，注意返回。

74. 搜索二维矩阵

这题就相当于把一个有序数组存储为一个二维矩阵。可以用二维数组的映射在做。实际上在计算机存储中。二维数组的存储就是按照一维数组来存的。比如下标为(i,j)的元素的一维数组下标就是i * nums[0].size + j。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int sz = matrix.size() * matrix[0].size();
        int left = 0, right = sz - 1;
        while(left <= right){
            int middle = (right - left) / 2 + left;
            //将middle一维下标转化为二维下标
            int mx = middle / matrix[0].size(), my = middle % matrix[0].size();
            if(matrix[mx][my] < target){
                left = middle + 1;
            }else if(matrix[mx][my] > target){
                right = middle - 1;
            }else{
                return true;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

再试试分别比较，做两次二分，想让target与每行最后一个比较， 再在每一行做一个二分：

class Solution {
public:
    bool searchMatrix(vector<vector<int>> matrix, int target) {
        auto row = upper_bound(matrix.begin(), matrix.end(), target, [](const int b, const vector<int> &a) {
            return b < a[0];
        });
        if (row == matrix.begin()) {
            return false;
        }
        --row;
        return binary_search(row->begin(), row->end(), target);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13