二分查找

灵茶山艾府的题单。

一、二分查找

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

方法一：双指针

方法二：二分查找

找到符合target的数值，分别向左和向右找到边界。

这里给出了一种用开区间的二分查找方法（第一次见）：

// 通过这个函数可以找到第一个目标值（如果存在）
// 可以找到第一个比当前值大的数（如果不存在）
int lower_bound(vector<int>& nums, int target) {
    int left = -1, right = nums.size();
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        (nums[mid] >= target ? right : left) = mid;
    }
    return right;
}

35 搜索插入位置

直接套用二分查找即可。

704 二分查找

直接套用二分查找即可。

35与704的细微区别，35只需要返回target在数组中的位置或者应该插入的位置，所以不需要考虑下标越界的问题。

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

直接套用二分查找即可。

2529 正整数和负整数的最大计数

分别查找0，1在数组中的位置即可。

2389 和有限的最长子序列

// 二分查找的库函数使用方法
// 注意：返回的都是迭代器！！！！

ranges::lower_bound(vector<int> nums, int target)
ranges::lower_bound(auto nums.begin(), auto nums.begin() + j, int target) //当范围是子数组时
// 查找第一个大于或等于给定值的元素位置
// 如果找到符合条件的元素，返回指向该元素的迭代器；否则返回范围的末尾迭代器（end()）

ranges::upper_bound(vector<int> nums, int target)
// 查找第一个大于给定值的元素位置
// 如果找到符合条件的元素，返回指向该元素的迭代器；否则返回范围的末尾迭代器（end()）

1170 比较字符串最小字母出现频次

这一题是在查找的背景外套了一层查找字符串中最小字母的皮。

2080 区间内查询数字的频率

这一题的主要问题出在需要声明一个类上面，leetcode的类声明使用了语法糖的方法，将”class”等省略了。第一次接触没看懂。。。。

2563 统计公平数对的数目

这一题里二分查找的调用是在子数组中，需要考虑到这一点。

2070 每一个查询的最大美丽值

思路一

暴力方法。双重循环，遍历每一个queries，再遍历一遍二维数组，找到合适的最大值。

思路二

因为要使用二分查找，所以必须先要满足有序的条件，对原二维数组进行排序。

在满足二维数组中第一列有序的情况下，这里有两种思路

• 前缀最大值

  可能会出现这样的情况，前缀在递增的时候美丽值反而变小了。发生这个情况的时候，反而会取前面美丽值更大的数组对。所以这里采用将数组中第二个值按照递增序取最大值覆盖的方法

• 去除无用信息

  同理，因为不用考虑第一个数值更大，美丽值反而小的数，所以将这个数组对删除即可

ranges::upper_bound(items, q, {}, [](auto& item) { return item[0]; })
// 参数解释
// items 已经排序的容器
// q 要查找的目标值
// {} 比较函数，{}表示使用默认比较
// [](auto& item){return item[0];} 投影函数，从每个元素item中提取用于比较的键 lambda表达式

二、二分答案

1283 使结果不超过阈值的最小除数

这一题是要在范围内查找到符合条件的最大整数，所以可以使用二分查找的方法。

在范围的选择上，左阈值显然是0，右阈值选取了数组中的最大值。

2187 完成旅途的最少时间

这一题的最大问题也是在判断左右端点上，太容易越界了。

左端点：数组中的最小值

右端点：数组中的最小值 * 需要完成的趟数

// 使用 LL 后缀的目的是保证在计算过程中不会出现整数溢出或者类型不匹配的状况。
long long right = 1LL * min_t * totalTrips;

1011 在D天内送达包裹的能力

如何判断窗口的端点呢？

左端点：数组内的最大值

右端点：数组和

875 爱吃香蕉的王可王可

ts

// 借助扩展运算符...将数组展开成独立的参数
// Math.max()这个函数需要接受多个数值参数，而不是一个数组
const piles = [3, 5, 2];
let right = Math.max(...piles);

// for...of 循环
// 依次将数组中的每个元素赋值给常量p
for (const p of piles) {
    // 循环体
}