C++中如何使用vector进行二分查找

# 1. C++中vector的二分查找理论

### 2.1 二分查找算法原理

二分查找是一种高效的查找算法，它利用了数组或向量的有序性。其基本原理是将查找范围不断缩小，每次将查找范围对半分割，直到找到目标元素或确定其不存在。

算法步骤如下：

1. 初始化查找范围为整个数组或向量。
2. 计算查找范围的中间索引。
3. 比较目标元素与中间元素：
- 如果相等，则找到目标元素，返回其索引。
- 如果小于中间元素，则将查找范围缩小为中间索引之前的部分。
- 如果大于中间元素，则将查找范围缩小为中间索引之后的部。
4. 重复步骤2和3，直到找到目标元素或确定其不存在。

# 2. C++中vector的二分查找理论

### 2.1 二分查找算法原理

二分查找算法是一种高效的搜索算法，用于在有序数组中查找特定元素。其基本原理是将数组划分为两半，然后根据目标元素与数组中间元素的比较结果，确定目标元素在数组的哪一半中。重复此过程，直到找到目标元素或确定它不存在于数组中。

**算法流程：**

1. 初始化左右指针（left 和 right）分别指向数组的首尾元素。
2. 计算数组的中间索引 mid。
3. 比较目标元素与数组[mid]：
- 如果相等，则返回 mid。
- 如果小于，则将 right 更新为 mid - 1。
- 如果大于，则将 left 更新为 mid + 1。
4. 重复步骤 2-3，直到 left > right。
5. 如果 left <= right，则目标元素存在，返回 mid。否则，返回 -1。

### 2.2 C++中vector的二分查找函数

C++标准库中为vector容器提供了`std::binary_search`函数，用于执行二分查找。该函数接收三个参数：

- `vector<T>& vec`：要搜索的vector
- `const T& value`：要查找的目标元素
- `Compare comp = std::less<T>()`（可选）：比较函数，用于比较目标元素与vector元素

**函数原型：**

bool std::binary_search(vector<T>& vec, const T& value, Compare comp = std::less<T>());

**返回结果：**

- `true`：如果目标元素存在于vector中
- `false`：如果目标元素不存在于vector中

**代码示例：**

#include <vector>
#include <algorithm>

int main() {
  vector<int> vec = {1, 3, 5, 7, 9, 11, 13, 15};
  int target = 7;

  // 使用默认比较函数
  bool found = std::binary_search(vec, target);

  // 使用自定义比较函数
  auto comp = [](int a, int b) { return a > b; };
  bool found_descending = std::binary_search(vec, target, comp);

  return 0;
}

**逻辑分析：**

* 第一行创建了一个包含整数元素的vector。
* 第二行定义了要查找的目标元素。
* 第三行使用默认比较函数对vector执行二分查找。
* 第五行定义了一个自定义比较函数，用于按降序对vector元素进行比较。
* 第六行使用自定义比较函数对vector执行二分查找。

# 3. C++中vector的二分查找实践

### 3.1 二分查找的步骤和实现

二分查找的步骤如下：

1. 初始化两个指针，`left` 和 `right`，分别指向向量的首尾元素。
2. 循环执行以下步骤，直到 `left` 大于 `right`：
- 计算中点 `mid` 为 `(left + right) / 2`。
- 比较目标值 `target` 与向量中 `mid` 处的元素 `vec[mid]`：
- 如果 `target` 等于 `vec[mid]`，则返回 `mid`。
- 如果 `target` 小于 `vec[mid]`，则将 `right` 更新为 `mid - 1`。
- 如果 `target` 大于 `vec[mid]`，则将 `left` 更新为 `mid + 1`。
3. 如果循环结束时 `left` 大于 `right`，则返回 `-1`，表示未找到目标值。

下面是 C++ 中使用 `std::vector` 实现二分查找的代码：

int binary_search(const std::vector<int>& vec, int target) {
  int left = 0;
  int right = vec.size() - 1;

  while (left <= right) {
    int mid = (left + right) / 2;

    if (vec[mid] == target) {
      return mid;
    } else if (vec[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

### 3.2 二分查找的性能分析

二分查找的平均时间复杂度为 O(log n)，其中 n 是向量的长度。这是因为在每次迭代中，二分查找都会将搜索范围减半。

下