c++简单实现的二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<vector>
#include<cstdlib>
#include<cctype>
int main(void) {
using namespace std;
vector<int> ar;
for (int i = 0; i < 10; i++)
    ar.push_back(i + 1);
vector<int>::const_iterator beg = ar.cbegin();
vector<int>::const_iterator end = ar.cend();
vector<int>::const_iterator mid = beg + (end - beg) / 2;
int guess;
(cin >> guess).get();
/*当只剩最后2个迭代器时还没找到，beg会被设置成end或end被设置成mid(此时为首)
end是尾后迭代器,当end==beg说明容器为空
*/
while (mid != end && *mid != guess) {
    if (guess < *mid)
        end = mid;
    else
        beg = mid + 1;
    mid = beg + (end - beg) / 2;
}
if (mid != end)//最好不要判断*mid 当mid==end时 *mid是未定义的
    cout << "Found." << endl;
else
    cout << "Unfound." << endl;
system("pause");
}

注意vector的end迭代器指向最后一个元素之后的内存，不要解引它！

引用自知乎

因为STL中的begin和end定义的是一个半开放区间“[begin, end)”，end是最后一个元素的后一个位置。这样做有两个好处：1，判断是否到尾部简单只要!=end就行了，<运算在STL中是要避免的，因为计算量可能会比较大。2，判断空区间很简单begin()==end()要取最后一个元素的话用last()方法。