lower_bound、upper_bound 和 last_less_equal。它們的作用是在 有序數組 中查找目標值的位置。下面是對每個函數的詳細解釋：
1. lower_bound 函數
功能：
在有序數組 a 中查找第一個 大于或等于 target 的元素的位置。
參數：
a[]：有序數組。n：數組的長度。target：目標值。
實現邏輯：
- 初始化左邊界
l = 0，右邊界r = n - 1。 - 使用二分查找：
- 計算中間位置
mid = l + (r - l) / 2。 - 如果
a[mid] >= target，說明目標值在左半部分，更新右邊界r = mid。 - 否則，目標值在右半部分，更新左邊界
l = mid + 1。
- 計算中間位置
- 最終返回
l，即第一個大于或等于target的位置。
示例：
int a[] = {1, 3, 5, 7, 9};
int n = 5;
int target = 5;
int pos = lower_bound(a, n, target); // 返回 2
2. upper_bound 函數
功能：
在有序數組 a 中查找第一個 大于 target 的元素的位置。
參數：
a[]：有序數組。n：數組的長度。target：目標值。
實現邏輯：
- 初始化左邊界
l = 0，右邊界r = n - 1。 - 使用二分查找：
- 計算中間位置
mid = l + (r - l) / 2。 - 如果
a[mid] > target，說明目標值在左半部分，更新右邊界r = mid。 - 否則，目標值在右半部分，更新左邊界
l = mid + 1。
- 計算中間位置
- 最終返回
l，即第一個大于target的位置。
示例：
int a[] = {1, 3, 5, 7, 9};
int n = 5;
int target = 5;
int pos = upper_bound(a, n, target); // 返回 3
3. last_less_equal 函數
功能：
在有序數組 a 中查找最后一個 小于或等于 target 的元素的位置。
參數：
a[]：有序數組。n：數組的長度。target：目標值。
實現邏輯：
- 調用
upper_bound函數，找到第一個大于target的位置。 - 返回
upper_bound(a, n, target) - 1，即最后一個小于或等于target的位置。
示例：
int a[] = {1, 3, 5, 7, 9};
int n = 5;
int target = 5;
int pos = last_less_equal(a, n, target); // 返回 2
4. 總結
lower_bound：查找第一個 大于或等于target的位置。upper_bound：查找第一個 大于target的位置。last_less_equal：查找最后一個 小于或等于target的位置。
這些函數在有序數組中非常有用，常用于解決 查找問題 或 范圍查詢問題。
5. 完整代碼
#include <iostream>
using namespace std;int lower_bound(int a[], int n, int target) {int l = 0, r = n - 1;while (l < r) {int mid = l + (r - l) / 2;if (a[mid] >= target) r = mid;else l = mid + 1;}return l;
}int upper_bound(int a[], int n, int target) {int l = 0, r = n - 1;while (l < r) {int mid = l + (r - l) / 2;if (a[mid] > target) r = mid;else l = mid + 1;}return l;
}int last_less_equal(int a[], int n, int target) {return upper_bound(a, n, target) - 1;
}int main() {int a[] = {1, 3, 5, 7, 9};int n = 5;int target = 5;cout << "lower_bound: " << lower_bound(a, n, target) << endl; // 輸出 2cout << "upper_bound: " << upper_bound(a, n, target) << endl; // 輸出 3cout << "last_less_equal: " << last_less_equal(a, n, target) << endl; // 輸出 2return 0;
}
6. 適用場景
- 查找問題：在有序數組中查找目標值的位置。
- 范圍查詢：查找滿足某個條件的元素范圍。
- 插入位置：確定目標值在有序數組中的插入位置。
這些函數是二分查找的經典應用，理解它們有助于解決許多算法問題。
