常用算法

常用算法

二分查找

三种： 普通 lower_bound upper_bound
找到 = 第一个 >= 第一个 >

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

进阶

满足二段性即可使用二分查找

不满足时候考虑恢复二段性

判断结果时,可用一个res直接接收,或者让闭区间的那边是属于结果的.

前缀和+二分查找

根据元素大于等于0，前缀和数组符合单调不减性， 可以使用二分。

有序集合+二分查找

当元素存在非正时， 可以使用有序集合来二分。

数学

数组\字符串左移\右移

二分查找博客

总结的很好, 我也分享一下我了解的吧.
除了楼主提到的模板题, 模板题还有(即C++中的lower_bound和upper_bound函数实现)

1. 直接定义res获取答案

可以避免陷入结果究竟是取l, l+1下标对应地元素等细节问题, 如29. 两数相除

class Solution {
public:
    bool mul(int x, int n, int comp) {
        int res = 0;
        while (n) {
            if (n & 1) {
                if (res < comp - x) {
                    return false;
                }
                res = res + x;
            }
            n >>= 1;
            if (n == 0)
                break;
            else if (x < comp - x)
                return false;
            x += x;
        }
        return true;
    }

    int divide(int a, int b) {
        if (a == INT_MIN) {
            if (b == -1) {
                return INT_MAX;
            } else if (b == 1) {
                return INT_MIN;
            }
        }
        bool rev = false;
        if (a > 0) {
            a = -a;
            rev = !rev;
        }
        if (b > 0) {
            b = -b;
            rev = !rev;
        }
        int l = 0, r = INT_MAX;
        int res = 0;
        while (l <= r) {
            int mid = ((r - l) >> 1) + l;
            if (mul(b, mid, a)) {
                res = mid; //直接在符合条件的mid处, 设置为res
                if (mid == INT_MAX) {
                    break;
                }
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return rev ? -res : res;
    }
};

题解本身有点复杂, 理解用res接收答案即可.
当然, 理解到底是哪个下标取答案是很有必要的, 对于二分查找的深入理解必不可少.

2. 二分查找的应用不止于单调性, 符合二段性即可

满足二段性即可使用二分查找
不满足时候可以考虑恢复二段性

通常来说, 需要定义一个check(mid)函数来判断移动left还是right, 如例题

3. 拓展

这部分对二分查找的应用需要对二分查找有一个很深的理解, 给出题目

LeetCode
常用算法
https://messenger1th.github.io/2024/07/24/LeetCode/常用算法/
作者
Epoch
发布于
2024年7月24日
许可协议