%%
# 纲要
> 主干纲要、Hint/线索/路标
# Q&A
#### 已明确
#### 待明确
> 当下仍存有的疑惑
**❓<font color="#c0504d"> 有什么问题？</font>**
# Buffer
## 闪念
> sudden idea
## 候选资料
> Read it later
%%
# 二分查找
二分查找是一种在**有序数组**中查找**特定元素**的高效算法。
其基本思想是，通过**取待查找区间的中点**，**将待查找的区间分成两半**，**判断待查找的元素是否在区间的==左半部分==或==右半部分==**，然后**迭代地在相应的半区间内查找**，从而**逐步缩小查找范围**，直至**找到目标元素**或**确定目标元素不存在**（待查找区间收缩为空）。
## 二分思想的本质——二段性
从本质上来说，「二分」的思想是利用 "**==二段性==**" 来进行排除——**=="有一段区间满足某个性质，而另一段区间不满足某个性质"==，则可应用 "二分" 进行==折半查找==，每次==排除其中一段/一半区间==，从而==缩小搜索范围==**。
通常来说，"可**应用二分查找**的前提条件是**被查找/搜索的「==目标序列==」 ==有序==，具有==单调性==**"，
但是， "**有序/单调性**" 并不是二分思想的**本质**，只是因为 **==有序序列==提供了这样的==二段性==**，
所以**能够在有序序列上运用二分搜索来查找目标值**。
<br>
## 有序序列上应用二分查找
在一个序列上**查找==序列中的某一目标值==** 时，**要求「目标序列」具有单调性**。
**只有这样，才能保证每次比较后，==一定能排除一半元素，从而缩小搜索范围**==。
> [!caution] 要求的是 "**被查找==目标==所构成的序列**" 必须有序，而不是**原序列**。
在部分场景下，**尽管==原序列有序==，但基于原序列各项元素所得的==新元素构成的序列==不一定有序，因此不能在这一==新序列==上进行二分查找**。
例如：
❌ 查找**有序数组中首个"值大于等于其下标"的元素**，**==不能==** 使用二分查找：
对每个 `i`，被查找的目标实际上是 `nums[i]>=i`，即 `nums[i]-i>=0` ，而 **`nums[i]-i` 并不保证有序**，因此**不能使用二分查找**。
例如对序数组 `{0, 1, 2, 2, 2, 5}` ，正确答案是 0，而 `nums[i]-i` 构成的新数组为 `{0, 0, 0, -1, -2, 0}`，不能应用二分查找。
✔️ 查找**升序数组中首个满足 `"nums[i]>=n-i"` 的元素**，可以使用二分查找：
对每个 `i`，**被查找的目标**实际上是 `nums[i]+i>=n`，`nums[i]` 和 `i` 都是升序的，
因此 `nums[i] + i` 也是有序的，**可以对 `nums[i] + i` 进行二分查找**。
✔️ 查找**降序数组中首个满足 `"nums[i]>= i+1"` 的元素**，可以使用二分查找：
对每个 `i`，**被查找的目标**实际上是 `nums[i]-i>=1`，**`nums[i]` 是降序**而 `i` 是升序的，
因此 `nums[i] - i` 仍然是降序的，**可以对 `nums[i] - i` 进行二分查找**。
<br><br>
# 二分查找的使用 ⭐
给定目标值 `k`，可在 **有序数组** 上查找（以**升序数组**为例）：
- **恰等于目标值 `k` 的元素下标**
- **左边界**：
- **`>=k`** 的 **==最小==** 元素下标
- **`>k`** 的 **==最小==** 元素下标：
- **右边界**：
- **`<=k`** 的 **==最大==** 元素下标：
- `<k` 的 **==最大==** 元素下标`
## 找目标值
###### 检查 `==k` 是否存在
```cpp
bool exist = binary_search(arr.begin(), arr.end(), k);
return exit;
```
###### 找值 `==k` 的**最小**下标（相当于找**左边界**）
注意：必须检查**位置是否==有效==(`!=arr.end()`)** & 检查 **`lower_bound(k)`是否==恰等于 k==**。
```cpp
int idx = lower_bound(arr.begin(), arr.end(), k) - arr.begin();
if (idx != n && arr[idx] == k) { // 检查下标有效 & arr[idx]恰为k
return idx; // arr[idx] == k.
}
return -1; // 不存在k
```
###### 找值 `==k` 的**最大**下标（相当于找**右边界**）
注意：必须检查**位置是否==有效==(`!=arr.begin()`)** & 检查 **`upper_bound(k) - 1`是否==恰等于 k==**。
> [!NOTE] `upper_bound()` 找大于`k` 的首项，相当于得到的是 **==右开边界==**：`[, r)`
```cpp
int idx = upper_bound(arr.begin(), arr.end(), k) - arr.begin();
if (idx != 0 && arr[idx - 1] == k) {
return idx - 1; // arr[idx - 1] == k.
}
return -1; // 不存在k
```
## 查找左边界
###### 找值 `>=k` 的最小下标
```cpp
int idx = lower_bound(arr.begin(), arr.end(), k) - arr.begin();
if (idx != n) return idx;
reutrn -1; // 不存在, 元素全<k.
```
###### 找值 `>k` 的最小下标
```cpp
int idx = upper_bound(arr.begin(), arr.end(), k) - arr.begin();
if (idx != n) return idx;
return -1; // 不存在, 元素全<=k.
```
## 查找右边界
对"**右边界**'" 的求解，均可**转换为对 "==左边界==" 的求解**。
- 「**`< k` 的最大元素下标**」 等价于「**`>=k` 的最小元素下标 ==- 1==**」
- 「**`<=k` 的最大元素下标** 」等价于「**`> k` 的最小元素下标 ==- 1==** 」
###### 找值 `<k` 的最大下标
```cpp
int idx = lower_bound(arr.begin(), arr.end(), k) - arr.begin();
if (idx != 0) return idx - 1; //
reutrn -1; // 不存在, 元素全>=k.
```
###### 找值 `<=k` 的最大下标
```cpp
int idx = upper_bound(arr.begin(), arr.end(), k) - arr.begin();
if (idx != 0) return idx - 1;
return -1; // 不存在, 元素全 > k.
```
## 查找范围
> [!example] 示例：[[99-题解/leetcode/lc-34 在排序数组中查找元素的第一个和最后一个位置|lc-34 在排序数组中查找元素的第一个和最后一个位置]]
###### 找值 `==k` 的区间范围 `[l, r)`
```cpp
int l = lower_bound(arr.beign(), arr.end(), k) - arr.begin(); // nums[l]>=k 的最小l.
int r = upper_bound(arr.begin(), arr.end(), k) - arr.begin(); // nums[r] >k 的最小r.
int length = r - l; // 区间[l, r)长度为 r - l.
```
- 若 `nums` 中所有元素均 `< k`，则 `l==r==n`，此时区间为空；
- 若 `nums` 中所有元素均 `> k`，则 `l==r==0`，此时区间也为空。
###### 找值 `lo <= val <= hi` 的区间范围 `[l, r)`
```cpp
int l = lower_bound(arr.beign(), arr.end(), lo) - arr.begin(); // nums[l]>=lo 的最小l.
int r = upper_bound(arr.begin(), arr.end(), hi) - arr.begin(); // nums[r] >hi 的最小r.
int length = r - l; // 区间[l, r)长度为 r - l.
```
## 查找最接近的值
查找数组中 **==最接近== `k` 的值**的下标位置：
1. 找 `k` **右侧（`>k`）与其最接近的值**的下标位置 `hi`，
则 `k` **左侧及本身（`<=k`）与其最接近的值**的下标位置 `lo = hi - 1`。
2. **比较 `arr[hi]` 与 `arr[hi-1]` 谁==更接近==** `k`。
```cpp
int min_diff = INT_MAX;
int hi = upper(arr.begin(), arr.end(), k) - arr.begin();
if (hi != n) {
min_diff = arr[hi] - k;
}
if (hi != 0) {
min_diff = min(min_diff, k - arr[hi-1]);
}
// 也可以是hi = lower(arr.begin(), arr.end(), k) - arr.begin();
```
## 统一使用 `lower_bound`
> [!NOTE] 在整数数组中，四种情况全都可以**统一为==基于 `lower_bound()` 求解==**：
>
> - 「**`> k` 的最小元素下标**」 等价于「**`>=(k+1)` 的最小元素下标**」
> - 「**`<=k` 的最大元素下标** 」等价于「**`>=(k+1)` 的最小元素下标 ==- 1==** 」
> - 「**`< k` 的最大元素下标**」 等价于「**`>=k` 的最小元素下标 ==- 1==**」
在 **==整数==** 数组中，**查找左右边界（`≥, >, <, ≤` 目标值`k`的四种情况）都可以直接基于 `lower_bound(k)` 解决**：
* `≥ k` 的最小元素下标（**左**边界）：`lower_bound(k)`
* `> k` 的最小元素下标（**左**边界）：`lower_bound(k+1)` 或 `upper_bound(k)`；
* `< k` 的最大元素下标（**右**边界）：`lower_bound(k)-1` 即**大于等于`k`的首项元素的左侧一项**。
* 若 `lower_bound(k) != arr.begin()`，则存在。
* `≤ k` 的最大元素下标（**右**边界）：`lower_bound(k+1)-1` 或 `upper_bound(k)-1`，即**大于`k`的首项元素的左侧一项**。
* 若 `lower_bound(k+1)` 或 `upper_bound(k)` 满足 `!=arr.begin()`，则存在。
- `== k` 的最小元素下标（**左**边界）：`lower_bound(k)` & 检查**是否==有效==(`!=arr.end()`)** & 检查 **`lower_bound(k)`是否==恰为 k==**
- `== k` 的最大元素下标（**右**边界）：`lower_bound(k+1)` & 检查**是否==有效== `!=arr.begin()`** & 检查 `lower_bound(k+1)-1` **是否==恰为`k`==**
> [!caution] 注意找「右边界」时的越界判断
> 通过`lower_bound(k) - 1` 以及 `upper_bound(k) - 1`找**右边界时**：
> - 若 `lower_bound(k)` 或 `upper_bound(k)` 返回 `arr.end()` ，**==减一的位置==也是==有效==的**。
> - 仅当 `lower_bound(k)` 或 `upper_bound(k)` 返回 `arr.begin()` 时，意味着**未找到/不存在**，此时**再`-1` 会==越界==**。
<br><br><br>
# 二分查找模版
![[00-数据结构与算法笔记/基本算法/二分查找模版.canvas|二分查找模版]]
## 二分查找的实现
根据以下对「**==循环不变量==** 」定义的不同，二分查找有多种不同的具体实现方式，各种方式的细节处理不同。
- 「区间」的含义：
- "**剩余未检查的区间**" ，当 `mid` 恰为查找目标时，**区间要==跳过 `mid`，不包含==**； ❇️
- "**答案可能存在的区间**"，当 `mid` 恰为查找目标时，**区间要==包含 `mid`==**；
- 「区间」的形式：
- **左闭右开区间** 或 **闭区间**
> [!tip] 推荐对区间的定义采用 "**==剩余未检查的区间==**"，这样无论是**闭区间还是开区间**，**`mid` 都无需向上取整**。
>
> MinGW 中对 `lower_bound()` 的实现逻辑里，循环条件即是 "**==剩余未检查区间==**"。不同在于，它的 **`mid` 采用了上取整**。
>
> ![[_attachment/00-数据结构与算法笔记/基本算法/二分查找.assets/IMG-二分查找-DEEC93A9250C837FCCA4BB6D737AB77E.png|950]]
>
> [!caution] 第二种区间含义（区间内包含可能的目标）存在瑕疵：
>
> - **当 `mid` 满足条件而需要收缩左边界**时（例如找 `>=mid` 的最后一项元素），需要取 `l == mid`，若元素数量≤2，则这在 `mid` 向下取整时会导致死循环，因此对应的 **`mid` 必须采用==上取整==** 。
>
> >
> - 当采用左闭右闭区间写法时循环条件应为`while (l < r)`，最后收缩到`l==r` 而跳出循环后需要**再额外进行一次 `check()` 判断最终结果，这个`check()`调用本身可能很耗时**.
> [!caution] 循环不变量定义采用 "答案可能存在的区间" 时，需要特别注意边界，避免死循环
>
> 为避免死循环，思考清楚下列两种特殊情况即可：
>
> - **`l` 和 `r` ==相邻==** 时，是否可能陷入死循环？
> - 如果可能，**则 `mid` 下取整还是上取整能避免死循环？**
> - **`l` 和 `r` ==重合==** 时，是否可能陷入死循环？
> - 如果可能，则 **`l==r`时需要==跳出循环==单独判断**
<br><br>
# 「左闭右开」区间表示"剩余待搜索区间"
循环不变量： `[l, r)` 表示**剩余==待搜索==区间**：
- **初始化**： `l = 0, r = n;`
- **循环条件**：`l < r` ，表示**还存在剩余待搜索空间**。
- **循环结束**时：`l == r`
- 找 **==左==边界**：升序数组中**找 `>=k` 或 `>k` 的 "==最小下标==元素"**
- 每当 `mid` 为目标值时 **`r` 都会收缩至 `r = mid`**； （取 `r`）
- 因此最终**若 ==`r != n`== 则 ==`r`== 即为所查找的目标**。
- 若目标不存在，则 `l` 一直会收缩至 `l==r==n`（越界）
- 找 **==右==边界**：升序数组中**找 `<= k` 或 `<k` 的 "==最大下标==元素"**
- 每当 `mid` 为目标值时 **`l` 都会收缩至 `l = mid+1`**，（取 `l - 1`）
- 因此最终**若 ==`l != 0`== 则 ==`l - 1`== 即为所查找的目标**。
- 若目标不存在，则 `r` 一直会收缩至 `l==r==0` ，此时 `l-1` 越界 ^1dce49
![[Excalidraw-Solution/二分查找_0.excalidraw.svg|550]]
%%[[Excalidraw-Solution/二分查找_0.excalidraw.md|🖋 Edit in Excalidraw]]%%
> [!caution] 如果 `n` 的范围是 `n <= INT_MAX`，则必须用 `long long` 来处理， <br> 否则无法表示右开边界 `r == INT_MAX + 1`
##### 找目标值
```cpp
// 查找值恰为k的元素的下标.
int BinarySearch(vector<int>& arr, int k) {
int l = 0, r = arr.size();
while (l < r) {
int mid = l + (r - l) / 2;
if (arr[mid] == k) {
return mid;
} else if (arr[mid] < k) {
l = mid + 1;
} else {
r = mid;
}
}
return -1;
// 如果要求未找到时返回可插入位置, 则直接return l或r.(会是-1或者n)
}
```
##### 找左边界
```cpp
// 找值大于等于k的最小下标
int lower_bound(vector<int>& arr, int k) {
int n = arr.size();
int l = 0, r = n;
while (l < r) {
int mid = l + (r - l) / 2;
if (arr[mid] >= k) {
r = mid;
} else {
l = mid + 1;
}
}
if (r != n) return r;
return -1;
// 若不存在>=k的元素, 则l收缩到l==r==n
// 若要求未找到时返回可插入位置(即n), 则直接return l或r.
}
// 找值大于k的最小下标
int upper_bound(vector<int>& arr, int k) {
int n = arr.size();
int l = 0, r = n;
while (l < r) {
int mid = l + (r - l) / 2;
if (arr[mid] > k) {
r = mid;
} else {
l = mid + 1;
}
}
if (r != n) return r;
return -1;
// 如果要求未找到时返回可插入位置(即n), 则直接return l或r.
}
```
##### 找右边界
```cpp
// 找值小于等于k的最大下标
int r_le_bound(vector<int>& arr, int k) {
int n = arr.size();
int l = 0, r = n;
while (l < r) {
int mid = l + (r - l) / 2;
if (arr[mid] <= k) {
l = mid + 1;
} else {
r = mid;
}
}
if (l != 0) return l - 1;
return -1;
// 如果要求未找到时返回可插入位置(即-1), 则直接return l - 1;
}
// 找值小于k的最大下标
int r_lt_bound(vector<int>& arr, int k) {
int n = arr.size();
int l = 0, r = n;
while (l < r) {
int mid = l + (r - l) / 2;
if (arr[mid] < k) {
l = mid + 1;
} else {
r = mid;
}
}
if (l != 0) return l - 1;
return -1;
// 如果要求未找到时返回可插入位置(即-1), 则直接return l - 1;
}
```
<br><br>
# 「左闭右闭」区间表示 "剩余待搜索区间"
循环不变量： `[l, r]` 表示**剩余==待搜索==区间**：
- **初始化**： `l = 0, r = n - 1;`
- **循环条件**：==`l <= r`==，表示**还存在剩余待搜索空间**
- **循环结束**时：`l == r + 1`
- 找 **==左==边界**：升序数组中**找 `>=k` 或 `>k` 的 "==最小下标==元素"**
- 每当 `mid` 为目标值时 **`r` 都会收缩至 `r = mid - 1`**，因此最终**若 ==`l != n`== 则 ==`l`==（也即`r + 1`） 即为所查找的目标**。
- 若目标不存在，则最终 `l` 会收缩至 `l==r+1==n`（**越界**）
- 找 **==右==边界**：升序数组中**找 `<= k` 或 `<k` 的 "==最大下标==元素"**
- 每当 `mid` 为目标值时 **`l` 都会收缩至 `l = mid+1`**，因此最终**若 ==`l != 0`== 则 ==`l - 1`== 即为所查找的目标**。
- 若目标不存在，则最终 `r` 会收缩至 `r==l-1==-1` （**越界**）
![[Excalidraw-Solution/二分查找_1.excalidraw.svg|550]]
%%[[Excalidraw-Solution/二分查找_1.excalidraw.md|🖋 Edit in Excalidraw]]%%
> [!caution] 如果 `n` 的范围是 `n <= INT_MAX`，则必须用 `long long` 来表示，或者在 `l == INT_MAX` 并且即将越界时跳出。
>
##### 找目标值
```cpp
int BinarySearch(std::vector<int>& arr, int k) {
int l = 0, r = arr.size() - 1;
while (l <= r) {
int mid = l + (r - l)/2;
if (arr[mid] < k) {
l = mid + 1;
} else if (arr[mid] > k) {
r = mid - 1;
} else {
return mid;
}
}
return -1;
}
```
##### 找左边界
```cpp
// 找值大于等于k的最小下标
int lower_bound(std::vector<int>& arr, int k) {
int n = arr.size();
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] >= k) {
r = mid - 1;
} else {
l = mid + 1;
}
}
if (l == n) return -1;
return l;
// 若不存在>=k的元素, 则l收缩到l==r+1==n.
// 若要求未找到时返回可插入位置(即n), 则直接return l或r+1.
}
// 找值大于k的最小下标
int upper_bound(std::vector<int>& arr, int k) {
int n = arr.size();
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] > k) {
r = mid - 1;
} else {
l = mid + 1;
}
}
if (l == n) return -1; // 若不存在>=k的元素, 则l收缩到l==r+1==n.
return l;
}
```
##### 找右边界
```cpp
// 找值小于等于k的最大下标
int r_le_bound(std::vector<int>& arr, int k) {
int n = arr.size();
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] <= k) {
l = mid + 1; // mid满足, 剩余区间[mid+1, r]待搜索. 明确l-1满足条件
} else {
r = mid - 1;
}
}
// 最后l==r+1, 若存在满足条件的目标, r即为目标下标; 否则, r收缩至r==l-1==-1.
return r;
}
// 找值小于k的最大下标
int r_lt_bound(std::vector<int>& arr, int k) {
int n = arr.size();
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] < k) {
l = mid + 1; // mid满足, 剩余区间[mid+1, r]待搜索. 明确l-1满足条件
} else {
r = mid - 1;
}
}
// 最后l==r+1, 若存在满足条件的目标, r即为目标下标; 否则, r收缩至r==l-1==-1.
return r;
}
```
<br><br>
# 「左闭右闭」区间表示 "答案可能存在的区间"
循环不变量： `[l, r]` 表示 **==包含可能答案的区间==**：
- **初始化**： `l = 0, r = n - 1;`
- **循环条件**：==`l < r`==，
- 若 `l != r`，表示**还需要进一步收缩可能存在答案的空间**
- 当 `l == r` 时，表示**只剩下这唯一的位置==可能包含答案==**，需**跳出循环，单独判断**。
- **循环结束**时：`l == r`
- 在循环体外，需要 **==再进行一次 `check`==**，判断最终 **`l==r` 的位置是否即为目标值**。
> [!NOTE]
>
> 在前两种**开区间/闭区间**写法中，区间本身表示的是 "**剩余待搜索的空间**"，因此当空间收缩到为空时，表示整个区间都已搜寻过，通过**判断边界位置是否越界即知答案是否存在**。
>
> 而在当前这种写法中，区间 `[l, r]` 表示的是 **==包含可能答案的区间==**，因此当最后 `l==r` 时，**==可能包含答案的空间收缩为 1==**，此时**需跳出循环（避免死循环）**，**==单独对这一个位置==检查是否包含目标值**。
- 找 **==左==边界**：升序数组中**找 `>=k` 或 `>k` 的 "==最小下标==元素"**
- `mid` 下取整
- **区间 `[l, r]` 被划分成 ==`[l, mid]`== 和 ==`[mid + 1, r]`==** ，每次 **==排除掉其中一半区间==**。
- 若 `mid` 满足条件，则排除右半区间 `[mid+1, r]`，收缩 `r = mid`；
- 若 `mid` 不满足，则排除左半侧区间 `[l, mid]`，收缩 `l = mid+1`；
- 当 `l==r`时跳出循环，**检查 `arr[l]` 是否为查找目标**；
- 注意检查**数组非空**：`n > 0 && check(arr[l]);`
- 找 **==右==边界**：升序数组中**找 `<= k` 或 `<k` 的 "==最大下标==元素"**
- **`mid` ==上取整==（`mid = l + (r - l + 1) / 2`）**
- **区间 `[l, r]` 被划分成 ==`[l, mid - 1]`== 和 ==`[mid, r]`==** ，每次 **==排除掉其中一半区间==**。
- 若 `mid` 满足条件，则排除左半区间 `[l, mid - 1]`，收缩 `l = mid`；
- 若 `mid` 不满足，则排除右半侧区间 `[mid, r]`，收缩 `r = mid - 1`；
- 当 `l==r`时跳出循环，**检查 `arr[l]` 是否为查找目标；
- 注意检查**数组非空**：`n > 0 && check(arr[l]);`
![[Excalidraw-Solution/二分查找_2.excalidraw.svg|550]]
%%[[Excalidraw-Solution/二分查找_2.excalidraw.md|🖋 Edit in Excalidraw]]%%
##### 找目标值
```cpp
int binary_search(vector<int>& arr, int k) {
int n = arr.size();
int l = 0, r = n - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (arr[mid] == k) {
return mid;
} else if (arr[mid] < k) {
l = mid + 1;
} else {
r = mid;
}
}
return (n > 0 && arr[l] == k) ? l : -1;
}
```
##### 找左边界
```cpp
int lower_bound(vector<int>& arr, int k) {
int n = arr.size();
int l = 0, r = n - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (arr[mid] >= k) {
r = mid;
} else {
l = mid + 1;
}
}
return (n > 0 && arr[l] >= k) ? l : -1;
// 如果要求未找到时返回可插入位置(即n), 则需要return l + 1.
}
int upper_bound(vector<int>& arr, int k) {
int n = arr.size();
int l = 0, r = n - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (arr[mid] > k) {
r = mid;
} else {
l = mid + 1;
}
}
return (n > 0 && arr[l] > k) ? l : -1;
// 如果要求未找到时返回可插入位置(即n), 则需要return l + 1.
}
```
##### 找右边界
```cpp
int r_le_bound(vector<int>& arr, int k) {
int n = arr.size();
int l = 0, r = n - 1;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (arr[mid] <= k) {
l = mid;
} else {
r = mid - 1;
}
}
return (n > 0 && arr[l] <= k) ? l : -1;
// 如果要求未找到时返回可插入位置(即-1), 则需要return l - 1.
}
int r_lt_bound(vector<int>& arr, int k) {
int n = arr.size();
int l = 0, r = n - 1;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (arr[mid] < k) {
l = mid;
} else {
r = mid - 1;
}
}
return (n > 0 && arr[l] < k) ? l : -1;
// 如果要求未找到时返回可插入位置(即-1), 则需要return l - 1.
}
```
##### 例题
[[99-题解/leetcode/lc-1533 找到最大整数的索引|lc-1533 找到最大整数的索引]]
<br><br>
# C++标准库中提供的二分查找函数
C++标准库提供了**四个二分查找**相关的函数：
- `upper_bound(first, last, val);`
在**升序序列** 区间 `[first, last)` 中二分查找并返回首个**元素值==大于== `val` 的位置**（左边界）
不存在时，返回 `last`；
- `lower_bound(first, last, val);`
在**升序序列** 区间 `[first, last)` 中二分查找并返回首个**元素值==大于等于== `val` 的位置**（左边界）
不存在时，返回 `last`；
- `binary_search(first, last, val);`
在**序列**区间 `[first, last)` 中二分查找，检查**是否存在目标值 `val`**，返回 `true/false`；
- `equal_range(first, last, val);`
在**序列**区间 `[first, last)` 中二分查找，得到一个**元素值全等于目标值 `val` 的区间范围**，
- 返回 `pair<ForwardIt, ForwardIt>` 类型的结果 `{begin}`
`{lower_bound(first, last, val), upper_bound(first, last, val)}`
> [!NOTE] `equal_range()` 使用示例
>
> ```cpp
> auto p = equal_range(nums.begin(), nums.end(), target);
> // 如果没有找到目标值，则返回{-1, -1}
> if (p.first == p.second) return {-1, -1};
> ```
---
搭配 `std::greater<T>()`，可用于在 **==降序==** 序列中进行二分查找：
- `lower_bound(first, last, val, std::greater<T>());`
在**降序序列**区间 `[first, last)` 中二分查找并返回首个**元素值==小于等于== `val` 的位置**（左边界）
- `upper_bound(first, last, val, std::greater<T>());`
在**降序序列**区间 `[first, last)` 中二分查找并返回首个**元素值==小于== `val` 的位置**（左边界）
<br>
### 函数原型
函数原型示例如下，默认使用 `std::less<T>()`，在 **==升序序列==** 中查找。
```cpp
template <class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value);
template <class ForwardIt, class T, class Compare>
ForwardIt upper_bound (ForwardIt first, ForwardIt last, const T& val, Compare comp);
template <class ForwardIt, class T, class Compare>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp);
template <class ForwardIt, class T, class Compare>
pair<ForwardIt,ForwardIt> equal_range(ForwardIt first, ForwardIt last, const T& value);
```
> ![[_attachment/00-数据结构与算法笔记/基本算法/二分查找.assets/IMG-二分查找-CA325BBBF83BF0399B678BB1AEF1DFD8.png|598]]
> ![[_attachment/00-数据结构与算法笔记/基本算法/二分查找.assets/IMG-二分查找-5C121B7F21FC7568280DB6458AC7817F.png|600]]
<br><br>
### 自定义 Compare 函数
- `lower_bound` 返回 `[first, last)` 区间中 ==`comp(*iter, value) == false`== 的 **首个位置**；
- 默认为`std::less`，即 `*iter < value == false` 的首个位置
- `upper_bound` 返回 `[first, last)` 区间中 ==`comp(value, *iter) == true`== 的**首个位置**；
- 默认为 `std::less`，即 `value < *iter == true` 的首个位置
%%
# 三分法
**「三分」就是使用两个端点将区间分成三份，然后通过每次否决三分之一的区间来逼近目标值。**
对于区间 `[l, r]`，划分成三等分 `[l, m1]`，`[m1, m2]`，`[m2, r]`：
- `m1 = l + (r - l) / 3;`
- `m2 = r - (r - l) / 3;`
%%
<br><br>
# 参考资料
[六款二分查找模板，哪款才是你的菜？](https://leetcode.cn/circle/discuss/ObmjbJ/)
[二分查找 红蓝染色法-灵茶山艾府\_哔哩哔哩\_bilibili](https://www.bilibili.com/video/BV1AP41137w7/?spm_id_from=333.788.recommend_more_video.4&vd_source=94d94bad947a5b38e63f1f55450429ab)
# Footnotes