首页 > > 程序设计 > C/C++ >

二分搜索

2018-06-17 23:19:53来源：未知阅读 ()

　　二分搜索从有序序列中寻找某个给定的值。二分搜索从中间位置开始搜索，如果中间位置的元素正好就是要找的元素，搜索完成；如果不是，假如该元素小于要找的元素，则在序列的后半部分继续搜索；假如该元素大于要找的元素，则在序列的前半部分继续搜索。在缩小的范围内计算一个新的中间元素并重复之前的过程，直至最终找到目标或者没有元素可供继续搜索（即未找到要搜索的元素）。

 1     //text 必须是有序的
 2     //beg 和 end表示我们搜索的范围
 3     auto beg = text.begin(), end = text.end();
 4     auto mid = text.begin() + (end - beg) / 2;    //初始状态下的中间点
 5     
 6     //当还有元素尚未检查并且我们还没有找到 sought 时执行循环
 7     while (mid != end && *mid != sought)
 8     {
 9         if (sought < *mid)                ///我们要找的元素在前半部分吗？
10         {
11             end = mid;                    //如果是，调整搜索范围使得忽略掉后半部分
12         }
13         else                            　//我们要找的元素在后半部分
14         {
15             beg = mid + 1;               //在 mid 之后寻找
16         }
17         mid = beg + (end - beg) / 2;      //新的中间点
18     }