理论第六课——二分查找函数

upper_bound：

在 STL 源码中，关于 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val) 函数的说明是这样的：

找到最后一个可以插入  val 而不改变原来有序数组的排序位置（Finds the last position in which  @p __val could be inserted without changing the ordering）。

在函数 *upper_bound(nums.begin(), nums.end(), 3) 的返回值中，指向了 4 也就是大于 3 的数，从 upper_bound(nums.begin(), nums.end(), 3) - nums.begin() 中可以看出返回来了 3 也就是第一个 4 的下标，因此 upper_bound() 函数可以理解为：大于目标元素的第一个数/位置。

 lower_bound：

对于 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val) 函数，STL 源码中是这样说的：

找到第一个可以插入  __val 的位置，并且不改变原有排序（Finds the first position in which  @a val could be inserted without changing the ordering.）。

字面上意思和 upper_bound 函数很像，都是为 val 找到一个可插入的位置，并不改变原来序列的有序性。但它和 upper_bound() 函数的最大不同在于找到的是 第一个 可插入的位置，而 upper_bound 找到的是 最后一个 可插入的位置。

总结：

upper_bound() 和 lower_bound() 函数实现的都是在有序序列中查找一个可插入的位置，插入后原序列有序性不变，但是：

upper_bound() 找到的是大于目标数的位置        lower_bound() 找到的是大于等于目标数的位置

那么下期再见（我保证下期不水了，主要是最近太忙了），拜拜！