C/C++语言的二分查找法及举例

忘了这是在哪里看到的一个练习题,也许对于好多人来说太简单了,自己写的时候修改了很多次才满意,感觉二分查找好像就是二叉树最早的原型吧,记录之

二分搜索算法
二分搜索算法用于针对已排序的集合进行搜索。
搜索结果需要满足以下要求:
1.如果有多个可匹配的值,则返回最大的那个索引。
2.如果没有找到,则返回失败的位置

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
31
32
33
34
35
36
#include <iostream>
#include <vector>

//该算法无法在匹配之后提前退出
template <typename T> std::size_t binSearch(const std::vector<T> &vec, const T &e)
{
std::size_t lo = 0, hi = vec.size(), mid = 0;
while (lo < hi) {
mid = (lo + hi) >> 1;
e < vec[mid] ? hi = mid : lo = mid + 1; //让lo最终定位在比所需匹配元素大一个索引的位置
}
return --lo;
}

int main(void)
{
std::vector<int> vec{1, 2, 4, 4, 4, 5, 5, 5, 5, 7, 9, 10, 10, 11};
std::cout << "Original array:" << std::endl;
std::cout << " Num: ";
for (auto v : vec)
std::cout << v << " ";
std::cout << std::endl << "Index: ";
for (int i = 0; i < vec.size(); ++i)
std::cout << i << " ";
int e, res;
std::cout << std::endl << "Enter your number: ";
while (std::cin >> e) {
res = binSearch<int>(vec, e);
if (vec[res] == e)
std::cout << "Ok: " << res << std::endl;
else
std::cout << "NO: " << res << std::endl;
std::cout << std::endl << "Enter your number: ";
}
return 0;
}