C++ 算法庫(5) 二分法查找操作

二分法查找操作：

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 <iostream>      // std::cout #include <algorithm>     // std::binary_search, std::sort #include <vector>        // std::vector bool myfunction ( int i, int j) {  return (i<j); } int main () {    int myints[] = { 1, 2, 3, 4, 5, 4, 3, 2, 1};   std::vector< int> 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 <iostream>      // std::cout #include <algorithm>     // std::equal_range, std::sort #include <vector>        // 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< int> v(myints,myints+ 8);                          // 10 20 30 30 20 10 10 20   std::pair<std::vector< int>::iterator,std::vector< int>::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; }

輸出：

1	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 <iostream>      // std::cout #include <algorithm>     // std::lower_bound, std::upper_bound, std::sort #include <vector>        // std::vector int main () {    int myints[] = { 10, 20, 30, 30, 20, 10, 10, 20};   std::vector< int> 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< int>::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/