力扣“二分查找”类型题目相关笔记

一、前言

代码随想录确实很好用，力扣刷题的顺序可以参考该网站。
很久没碰过算法题了，很多知识都忘了，就当复习了。

二、相关题目及相关知识点

1、704.二分查找

就是很简单的二分查找基础题，没什么好说的，就把二分查找的模板放这吧。

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

要注意mid值的计算方法，如果用mid = (right + left) / 2 的话有可能会产生溢出的情况。

2、35. 搜索插入位置

就是二分查找的微变形题目，因为题目中提到数组中无重复元素，所以比较简单，只需要找出target的位置然后输出就行，找不到target的位置直接输出left的值就可以。

tips：
二分查找中while的循环跳出条件是left>right的情况，所以最后right指向比target小的数，而left指向比target大的数，按照题目的插入要求，最后要输出left的值。

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

题目提示数组为“非递减的”，所以这个数组里面有重复元素，难度相对地提升了一些。
其实思路也很简单，就是找target的left值以及target+1的left值。

class Solution {
public:
    int search(vector<int>& nums, int target){
        int left = 0, right = nums.size() - 1;
        while(left <= right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] >= target){
                right = mid - 1; //这里的right就是帮助缩小范围的，帮助找到left
            }
            else left = mid + 1;
        }
        return left;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        int ansl = 0, ansr = nums.size() - 1;
        ansl = search(nums, target);
        if(ansl > ansr || nums[ansl] != target) 
            return vector<int>{-1, -1}; //这里就是利用ansr的初始值而已，没有其他含义
        ansr = search(nums, target + 1) - 1;

        return vector<int>{ansl, ansr};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4、69. x 的平方根

就是从0到x范围用二分法，试mid * mid == x。

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

要注意的就是mid需要用long long定义。
最后判断的时候之所以是x / left == left，是因为这时的left一定不是0，所以才可以这样用。

如果不想用long long 定义mid，可以参照x / left == left将其改为x / mid == mid，不过要在while之前把mid等于0的情况先剔除掉。

5、367. 有效的完全平方数

上一道题的很简单的一个变形。

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