C++标准库之 Lower_Bound, upper_Bound
关于二分查找，这绝对是最简单却又最难的实现了，其各种版本可以参见http://blog.csdn.net/xuqingict/article/details/17335833
在C++的标准库中，便提供了这样的函数，lower_bound 与 upper_bound，对于这两个函数的理解，有如下几种情形：
1 数组中包含至少一个目标元素，例如在下面数字中搜索数字3.
在该数组中搜索数字3，得到的low与high的结果如图所示：
其实这很简单 表示 [ low , high ) 这个半开半闭区间里面全部是3 。
2 原数组中不存在该元素呢，那么low与high返回的是什么呢，同样的例子，结果为：
可以看到，low与high均指向了4这个位置，可以直观的的解释为：
如果不存在目标元素，那么low表示的是第一个大于该目标元素的位置（也就是如果要插入目标元素，应该插入的位置），
high是同样的意思。
好了，这两函数的用法已经解析了，接下来看看其实现原理了:这其实就是一个简单的二分搜索，大致实现的代码如下：
在上述代码中，可以很清楚的看到，只是一个很简单的二分搜索的模板函数。
值得一提的是 :
1上面的triats可能有点儿吓到你了，请参考 http://blog.csdn.net/shoulinjun/article/details/19432007
2上面的代码使用了typename，别忘了 “嵌套从属定义”
同样的道理，可以实现upper_bound的代码如下：相信这些代码对于你而言，其实很简单，除了traits以及typename等的使用之外：
值得注意的是：
第一：上述代码中的迭代器是前向迭代器，因此可能你想象的代码的样子与上述是有差异的，但是请注意双向
迭代器以及随机迭代器是可以替代它的位置的，因为STL库用的是 “最小类型”的迭代器来定义该函数的。
第二：上述my_upper_bound中的 < 符号，为什么不能使用 > ，显然这里是不可以的，因为这样的话，你就
必须保证你传入的类型是支持operator< 以及 operator > 的，相信这个是画蛇添足了。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
