lower_bound

lower_bound 是 C++ 標準庫算法，通常用于有序序列中查找第一個不小于給定值的元素。它屬于 <algorithm> 頭文件，并且是基于二分查找實現(xiàn)的，因此要求輸入序列必須是有序的。

基本語法

#include <algorithm>  // 引入算法庫Iterator lower_bound(Iterator first, Iterator last, const T& value);

• first 和 last 是迭代器，分別表示容器的起始位置和結束位置（不包括 last）。

• value 是要在容器中查找的目標值。

• 返回值是迭代器，指向第一個不小于 value 的元素。如果沒有找到符合條件的元素，返回 last。

使用條件

• 容器中的元素必須是有序的，通常是按非遞減順序（從小到大）排列的。

• 如果容器無序，需要先對容器進行排序，才能使用 lower_bound。

返回值解釋

• 如果找到一個元素，其值不小于 value，返回指向該元素的迭代器。

• 如果所有元素都小于 value，返回 last，即容器的末尾。

示例代碼

示例 1：簡單查找

#include <iostream>
#include <vector>
#include <algorithm>  // 需要引入algorithmint main() {std::vector<int> v = {1, 2, 4, 4, 5, 8, 10};int value = 4;auto it = std::lower_bound(v.begin(), v.end(), value);if (it != v.end()) {std::cout << "第一個不小于 " << value << " 的元素是: " << *it << std::endl;} else {std::cout << "沒有找到不小于 " << value << " 的元素。" << std::endl;}return 0;
}

輸出：

第一個不小于 4 的元素是: 4

在這個例子中，lower_bound 返回了指向值為 4 的第一個元素的迭代器。

示例 2：未找到的情況

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> v = {1, 2, 4, 4, 5, 8, 10};int value = 12;auto it = std::lower_bound(v.begin(), v.end(), value);if (it != v.end()) {std::cout << "第一個不小于 " << value << " 的元素是: " << *it << std::endl;} else {std::cout << "沒有找到不小于 " << value << " 的元素。" << std::endl;}return 0;
}

輸出：

沒有找到不小于 12 的元素。

因為所有元素都小于 12，所以返回 v.end()。

注意事項

1. 容器必須有序：如果容器未排序，lower_bound 的結果是未定義的。

2. 時間復雜度：由于使用二分查找，時間復雜度為 O(logn)，其中 n 是容器中元素的數(shù)量。

3. 自定義比較函數(shù)：如果需要使用自定義的順序規(guī)則，可以提供一個比較函數(shù)作為參數(shù)，例如

   auto it = std::lower_bound(v.begin(), v.end(), value, custom_compare);

   其中 custom_compare 是一個函數(shù)對象，接收兩個元素作為參數(shù)，返回一個布爾值，用于定義排序規(guī)則。

lower_bound 是一個非常實用的函數(shù)，特別適合在有序數(shù)據(jù)中進行高效的查找操作。

upper_bound

upper_bound 是 C++ 標準庫中的一個算法函數(shù)，與 lower_bound 類似，它也用于有序序列中查找特定值的位置，但功能略有不同。upper_bound 用于查找第一個大于給定值的元素的位置。它同樣基于二分查找實現(xiàn)，因此要求輸入序列必須是有序的。

基本語法

#include <algorithm>  // 引入算法庫Iterator upper_bound(Iterator first, Iterator last, const T& value);

• first 和 last 是迭代器，分別表示容器的起始位置和結束位置（不包括 last）。

• value 是要在容器中查找的目標值。

• 返回值是迭代器，指向第一個大于 value 的元素。如果沒有找到符合條件的元素，返回 last。

使用條件

• 容器中的元素必須是有序的，通常是按非遞減順序（從小到大）排列的。

• 如果容器無序，需要先對容器進行排序，才能使用 upper_bound。

返回值解釋

• 如果找到一個元素，其值大于 value，返回指向該元素的迭代器。

• 如果所有元素都小于或等于 value，返回 last，即容器的末尾。

示例代碼

示例 1：簡單查找

#include <iostream>
#include <vector>
#include <algorithm>  // 需要引入algorithmint main() {std::vector<int> v = {1, 2, 4, 4, 5, 8, 10};int value = 4;auto it = std::upper_bound(v.begin(), v.end(), value);if (it != v.end()) {std::cout << "第一個大于 " << value << " 的元素是: " << *it << std::endl;} else {std::cout << "沒有找到大于 " << value << " 的元素。" << std::endl;}return 0;
}

輸出：

第一個大于 4 的元素是: 5

在這個例子中，upper_bound 返回了指向值為 5 的元素的迭代器。

示例 2：未找到的情況

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> v = {1, 2, 4, 4, 5, 8, 10};int value = 12;auto it = std::upper_bound(v.begin(), v.end(), value);if (it != v.end()) {std::cout << "第一個大于 " << value << " 的元素是: " << *it << std::endl;} else {std::cout << "沒有找到大于 " << value << " 的元素。" << std::endl;}return 0;
}

輸出：

沒有找到大于 12 的元素。

因為所有元素都小于或等于 12，所以返回 v.end()。

注意事項

1. 容器必須有序：如果容器未排序，upper_bound 的結果是未定義的。

2. 時間復雜度：由于使用二分查找，時間復雜度為 O(logn)，其中 n 是容器中元素的數(shù)量。

3. 自定義比較函數(shù)：如果需要使用自定義的順序規(guī)則，可以提供一個比較函數(shù)作為參數(shù)，例如

   auto it = std::upper_bound(v.begin(), v.end(), value, custom_compare);

   其中 custom_compare 是一個函數(shù)對象，接收兩個元素作為參數(shù)，返回一個布爾值，用于定義排序規(guī)則。

4. 與 lower_bound 的區(qū)別：

   • lower_bound 返回第一個不小于給定值的元素。

   • upper_bound 返回第一個大于給定值的元素。

   • 如果容器中存在多個相同的值，lower_bound 會返回第一個等于該值的元素，而 upper_bound 會返回第一個大于該值的元素。

應用場景

upper_bound 常用于以下場景：

• 在有序序列中查找第一個大于某個值的元素。

• 用于實現(xiàn)區(qū)間查找，例如結合 lower_bound 和 upper_bound 來查找某個值的范圍。