c++二分查找的方式

例

209. 长度最小的子数组o(nlogn)解法如下：

class Solution { public:     int minSubArrayLen(int s, vector<int>& nums) {         int n = nums.size();         if (n == 0) {             return 0;         }         int ans = INT_MAX;         vector<int> sums(n   1, 0);          // 为便于计算，令 size = n   1          // sums[0] = 0 意味着前 0 前缀和为 0         // sums[1] = A[0] 前 1 前缀和为 A[0]         // 以此类推         for (int i = 1; i <= n; i  ) {             sums[i] = sums[i - 1]   nums[i - 1];         }         for (int i = 1; i <= n; i  ) {             int target = s   sums[i - 1];             auto bound = lower_bound(sums.begin(), sums.end(), target);             if (bound != sums.end()) {                 ans = min(ans, static_cast<int>((bound - sums.begin()) - (i - 1)));             }         }         return ans == INT_MAX ? 0 : ans;     } };  作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/ 来源：力扣（LeetCode） 作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

说明

//在 [first, last) 区域搜索不小于 val 的元素 ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,                              const T& val); //在 [first, last) 第一个不符合区域的搜索 comp 规则的元素 ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,                              const T& val, Compare comp);

其中，first 和 last 都是正向迭代器，[first, last) 指定函数的作用范围；val 指定目标元素；comp 用于自定义比较规则的参数可以接收一个包含 2 个体参数(第二个形参数总是 val）且返回值为 bool 函数类型，可以是普通函数，也可以是函数对象。

//查找[first, last)第一个区域大于 val 的元素。 ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,                              const T& val); //查找[first, last)第一个不符合区域 comp 规则的元素 ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,                              const T& val, Compare comp);

由于 upper_bound() 底层实现采用二分搜索的方式，因此该函数仅适用于已排序序列。请注意，这里提到的已排序并不要求数据完全按照一定的排序规则进行升序或降序，而只需要 [first, last) 区域内所有令 element<val（或者 comp(val, element）成立元素位于不成立元素的前面(包括 element 为指定范围内的元素)。

equel_range() 函数：

//找到 [first, last) 范围内的一切都等于 val 的元素 pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

以上 2 种格式中，first 和 last 都是正向迭代器，[first, last) 指定函数的作用范围；val 指定目标值；comp 用于指定比较规则，该参数可以接收一个包含 2 个体参数(第二个形参数总是 val）且返回值为 bool 函数类型，可以是普通函数，也可以是函数对象。 同时，函数将返回到一个 pair 包括类型值 2 正向迭代器。当搜索成功时：

1. 第 1 迭代器指向 [first, last) 第一个等于区域 val 的元素；
2. 第 2 迭代器指向 [first, last) 第一个区域大于 val 的元素。

相反，如果你发现失败了，那这样 2 迭代器要么指向大于 val 第一个元素(如果有)，要么都和 last 迭代器指向相同的方向。

//查找 [first, last) 该区域是否包含 val bool binary_search (ForwardIterator first, ForwardIterator last,                       const T& val); //根据 comp 找到指定的规则 [first, last) 区域内是否包含 val bool binary_search (ForwardIterator first, ForwardIterator last,                       const T& val, Compare comp);

引用来自C equel_range()函数详解