C++ 算法库(5) 二分法查找操作 - c++编程基础

二分法查找操作：

`binary_search`	判断范围中是否存在值等价于给定值的元素
`equal_range`	返回范围中值等于给定值的元素组成的子范围
`lower_bound`	返回指向范围中第一个值大于或等于给定值的元素的迭代器
`upper_bound`	返回指向范围中第一个值大于给定值的元素的迭代器

binary_search

判断范围中是否存在值等价于给定值的元素

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

// binary_search example
#include // std::cout
#include // std::binary_search, std::sort
#include // std::vector

bool myfunction (int i,int j) { return (i
int main () {
int myints[] = {1,2,3,4,5,4,3,2,1};
std::vector v(myints,myints+9); // 1 2 3 4 5 4 3 2 1

// using default comparison:
std::sort (v.begin(), v.end());

std::cout << "looking for a 3... ";
if (std::binary_search (v.begin(), v.end(), 3))
std::cout << "found!\n"; else std::cout << "not found.\n";

// using myfunction as comp:
std::sort (v.begin(), v.end(), myfunction);

std::cout << "looking for a 6... ";
if (std::binary_search (v.begin(), v.end(), 6, myfunction))
std::cout << "found!\n"; else std::cout << "not found.\n";

return 0;
}

输出：

1
2

looking for a 3... found!
looking for a 6... not found.

equal_range

返回范围中值等于给定值的元素组成的子范围

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

// equal_range example
#include // std::cout
#include // std::equal_range, std::sort
#include // std::vector

bool mygreater (int i,int j) { return (i>j); }

int main () {
int myints[] = {10,20,30,30,20,10,10,20};
std::vector v(myints,myints+8); // 10 20 30 30 20 10 10 20
std::pair ::iterator,std::vector ::iterator> bounds;

// using default comparison:
std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30
bounds=std::equal_range (v.begin(), v.end(), 20); // ^ ^

// using "mygreater" as comp:
std::sort (v.begin(), v.end(), mygreater); // 30 30 20 20 20 10 10 10
bounds=std::equal_range (v.begin(), v.end(), 20, mygreater); // ^ ^

std::cout << "bounds at positions " << (bounds.first - v.begin());
std::cout << " and " << (bounds.second - v.begin()) << '\n';

return 0;
}

输出：

bounds at positions 2 and 5

lower_bound

返回指向范围中第一个值大于或等于给定值的元素的迭代器

upper_bound

返回指向范围中第一个值大于给定值的元素的迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// lower_bound/upper_bound example
#include // std::cout
#include // std::lower_bound, std::upper_bound, std::sort
#include // std::vector

int main () {
int myints[] = {10,20,30,30,20,10,10,20};
std::vector v(myints,myints+8); // 10 20 30 30 20 10 10 20

std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30

std::vector ::iterator low,up;
low=std::lower_bound (v.begin(), v.end(), 20); // ^
up= std::upper_bound (v.begin(), v.end(), 20); // ^

std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
std::cout << "upper_bound at position " << (up - v.begin()) << '\n';

return 0;
}

输出：

1
2

lower_bound at position 3
upper_bound at position 6

特别说明：函数的中文释义来自：http://classfoo.cn/cpp/head/76573_319/，例子来自：http://www.cplusplus.com/reference/algorithm/