C++标准库之 Lower_Bound, upper_Bound

关于二分查找,这绝对是最简单却又最难的实现了,其各种版本可以参见http://blog.csdn.net/xuqingict/article/details/17335833


在C++的标准库中,便提供了这样的函数,lower_bound 与 upper_bound,对于这两个函数的理解,有如下几种情形:


1   数组中包含至少一个目标元素,例如在下面数字中搜索数字3.

C++标准库之 Lower_Bound, upper_Bound

在该数组中搜索数字3,得到的low与high的结果如图所示:

其实这很简单  表示  [ low , high ) 这个半开半闭区间里面全部是3 。


2    原数组中不存在该元素呢,那么low与high返回的是什么呢,同样的例子,结果为:

C++标准库之 Lower_Bound, upper_Bound

可以看到,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 > 的,相信这个是画蛇添足了。




C++标准库之 Lower_Bound, upper_Bound,布布扣,bubuko.com

C++标准库之 Lower_Bound, upper_Bound

上一篇:java反射机制简介


下一篇:JAVA之File类 获取一个目录下的所有文件夹和文件,包括子文件夹和子文件