C++ lower_bound 函数用法

因为文本块不支持下划线，所以以下均打成 \(\text{lower-bound}\)。

虽然只是简单语法，但是我确实不太能记住。比如很多分块题要求在整块二分，此时如果能善用 \(\text{lower-bound}\) 函数就能少写一个二分。

然后本文只是作者自己看源代码理解的，当然是有不准确的地方。并且本文只会从算法竞赛的角度分析，如果你是程序员那建议不要看。

\(\text{lower-bound}\) 的平凡用法是在整数序列中找第一个大于 \(x\) 的位置，其中要求原序列必须有序。比如以下代码：

int a[5] = {1, 3, 4, 6, 7};
int que[5] = {0, 2, 3, 6, 8};
for (int i = 0; i < 5; ++i) {
  int x = que[i];
  auto it = lower_bound(a, a + 5, x);
  cout << it - x << ' '; 
}
cout << '\n';

输出为

0 1 2 3 5

注意 \(\text{lower-bound}\) 返回的是迭代器，如果要输出值的话可以用 *it。但是上面的代码改成输出 *it 会有问题，因为 it 在最后一次询问中会变成 a + 5，没注意的话可能就会 \(\text{RE}\)，这也是写代码时需要注意的地方。

但是如果真的这么简单的话，我也就不需要专门用一篇博客记录了。当然，\(\text{lower-bound}\) 还有更加高级的用法，你可以使用一个 lower_bound(b, e, x, cmp) 在找 b 到 e 中第一个不满足 cmp(a, x) 的元素 a 的位置，其中 cmp 可以是你自己定义的一个比较器。源代码为

template<typename _ForwardIterator, typename _Tp, typename _Compare>
    _ForwardIterator
    __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
		  const _Tp& __val, _Compare __comp)
    {
      typedef typename iterator_traits<_ForwardIterator>::difference_type
	_DistanceType;

      _DistanceType __len = std::distance(__first, __last);

      while (__len > 0)
	{
	  _DistanceType __half = __len >> 1;
	  _ForwardIterator __middle = __first;
	  std::advance(__middle, __half);
	  if (__comp(__middle, __val))
	    {
	      __first = __middle;
	      ++__first;
	      __len = __len - __half - 1;
	    }
	  else
	    __len = __half;
	}
      return __first;
    }

同理，upper_bound(b, e, x, cmp) 可以找到 b 到 e 中第一个满足 cmp(x, a) 的元素 a 的位置，其中 cmp 当然也可以自定义。源代码为：

template<typename _ForwardIterator, typename _Tp, typename _Compare>
    _ForwardIterator
    __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
		  const _Tp& __val, _Compare __comp)
    {
      typedef typename iterator_traits<_ForwardIterator>::difference_type
	_DistanceType;

      _DistanceType __len = std::distance(__first, __last);

      while (__len > 0)
	{
	  _DistanceType __half = __len >> 1;
	  _ForwardIterator __middle = __first;
	  std::advance(__middle, __half);
	  if (__comp(__val, __middle))
	    __len = __half;
	  else
	    {
	      __first = __middle;
	      ++__first;
	      __len = __len - __half - 1;
	    }
	}
      return __first;
    }

这样的话很多题的代码其实可以简单很多，因为可以重载 cmp 的话其实拓展空间挺大的。