> For the complete documentation index, see [llms.txt](https://fantasy-jxf.gitbook.io/artificial-intelligence/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/bei-wang-bi-bei-suan-fa.md).

# 必备算法

* 一些必备算法，主要是 C++ 版本

  Index
* [二分查找](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xB-O_6Po35PkZz9#二分查找)
  * [离散版](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xB-O_6Po35PkZz9#离散版)
    * [`my_binary_search(vector<int>, int)`](/artificial-intelligence/algorithm/bei-wang-bi-bei-suan-fa.md#my_binary_searchvectorint-int)
    * [`my_lower_bound(vector<int>, int)`](/artificial-intelligence/algorithm/bei-wang-bi-bei-suan-fa.md#my_lower_boundvectorint-int)
    * [`my_upper_bound(vector<int>, int)`](/artificial-intelligence/algorithm/bei-wang-bi-bei-suan-fa.md#my_upper_boundvectorint-int)
* [排序](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xB-O_6Po35PkZz9#排序)
  * [堆排序](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xB-O_6Po35PkZz9#堆排序)
    * [建堆的时间复杂度](https://fantasy-jxf.gitbook.io/artificial-intelligence/algorithm/pages/-LZy8xB-O_6Po35PkZz9#建堆的时间复杂度)

## 二分查找

### 离散版

#### `my_binary_search(vector<int>, int)`

* 没有重复元素时，目标值若存在，则返回索引；若不存在，返回 -1
* 存在重复元素时，目标值若存在，则返回最小索引；若不存在，返回 -1

  ```cpp
  int my_binary_search(vector<int>& nums, int v) {
      if (nums.size() < 1) return - 1;

      int lo = -1, hi = nums.size();  // hi = nums.size() - 1

      while (hi - lo > 1) {
          int mid = lo + (hi - lo) / 2;
          if (nums[mid] < v)
              lo = mid;
          else
              hi = mid;
      }

      return nums[lo + 1] == v ? lo + 1 : -1;
  }
  ```

#### `my_lower_bound(vector<int>, int)`

* 返回大于、等于目标值的最小索引（第一个大于或等于目标值的索引）

  ```cpp
  int my_lower_bound(vector<int>& nums, int v) {
      if (nums.size() < 1) return -1;

      int lo = -1, hi = nums.size();  // hi = nums.size() - 1

      while (hi - lo > 1) {                       // 退出循环时有：lo + 1 == hi
          int mid = lo + (hi - lo) / 2;
          if (nums[mid] < v)
              lo = mid;                           // 因为始终将 lo 端当做开区间，所以没有必要 `lo = mid + 1;`
          else
              hi = mid;                           // 而在 else 中，mid 可能就是最后的结果，所以不能 `hi = mid - 1`
      }

      return lo + 1; // 相比 binary_search，只有返回值不同
  }
  ```
* **为什么返回** `lo + 1`**？**
  * 模板开始时将 (lo, hi) 看做是一个开区间，通过不断二分，最终这个区间中只会含有一个值，即 (lo, hi]
  * 返回 lo+1 的含义是，结果就在 lo 的下一个；
  * 在迭代的过程中，hi 会从开区间变为闭区间，而 lo 始终是开区间，返回 lo+1 显得更加统一。
  * 当然，这跟迭代的写法是相关的，你也可以使最终的结果区间是 \[lo, hi)，这取决于个人习惯。

#### `my_upper_bound(vector<int>, int)`

* 返回大于目标值的最小索引（第一个大于目标值的索引）

  ```cpp
  int my_upper_bound(vector<int>& nums, int v) {
      if (nums.size() < 1) return -1;

      int lo = -1, hi = nums.size();  // hi = nums.size() - 1

      while (hi - lo > 1) {
          int mid = lo + (hi - lo) / 2;

          if (nums[mid] <= v)                     // 相比 lower_bound，唯一不同点：`<` -> `<=`
              lo = mid;
          else
              hi = mid;
      }

      return lo + 1;
  }
  ```

## 排序

### 堆排序

```cpp
```

#### 建堆的时间复杂度

> [为什么建立一个二叉堆的时间为O(N)而不是O(Nlog(N))?](https://www.zhihu.com/question/264693363/answer/291397356) - 知乎