关于二分查找,这绝对是最简单却又最难的实现了,其各种版本号能够參见http://blog.csdn.net/xuqingict/article/details/17335833
在C++的标准库中,便提供了这种函数,lower_bound 与 upper_bound,对于这两个函数的理解,有例如以下几种情形:
updated:
lower_bound与upper_bound类似于 “区间查找”,也就是说在一个有序的数组中找到元素target出现的区间[ left, right ),这里是一个半开半闭的区间。
left是第一个等于target的位置,right是最有一个等于target的位置的下一个位置!!
假设不存在该元素,那么right的含义不变。left与right指向同一个位置,该区间的大小此时为0!!!
lower_bound的实现是找到第一个等于target的位置,那么当mid元素小于target的时候,就须要一直往后走,找到该元素第一次出现的位置。
对于下述的二分查找的理解:
之前我还一直纳闷儿,为什么每次都是将target的值与*mid元素来比較时,仅仅比較target小于*mid的情况,是由于事实上终于的结果事实上是在寻找等于或者是大于target的部分。
1 数组中包括至少一个目标元素,比如在以下数字中搜索数字3.
在该数组中搜索数字3,得到的low与high的结果如图所看到的:
事实上这非常easy 表示 [ low , high ) 这个半开半闭区间里面所有是3 。
2 原数组中不存在该元素呢,那么low与high返回的是什么呢,相同的样例,结果为:
能够看到,low与high均指向了4这个位置,能够直观的的解释为:
假设不存在目标元素,那么low表示的是第一个大于该目标元素的位置(也就是假设要插入目标元素,应该插入的位置),
high是相同的意思。
好了,这两函数的使用方法已经解析了,接下来看看事实上现原理了:这事实上就是一个简单的二分搜索,大致实现的代码例如以下:
在上述代码中,能够非常清楚的看到,仅仅是一个非常easy的二分搜索的模板函数。
值得一提的是 :
1上面的triats可能有点儿吓到你了,请參考 http://blog.csdn.net/shoulinjun/article/details/19432007
2上面的代码使用了typename,别忘了“嵌套从属定义”
相同的道理,能够实现upper_bound的代码例如以下:相信这些代码对于你而言,事实上非常easy,除了traits以及typename等的使用之外:
值得注意的是:
第一:上述代码中的迭代器是前向迭代器,因此可能你想象的代码的样子与上述是有差异的,可是请注意双向
迭代器以及随机迭代器是能够替代它的位置的,由于STL库用的是 “最小类型”的迭代器来定义该函数的。
第二:上述my_upper_bound中的 < 符号,为什么不能使用 > ,显然这里是不能够的,由于这种话,你就
必须保证你传入的类型是支持operator< 以及 operator > 的,相信这个是画蛇添足了。