C++ 二分法查找元素及其索引

C++ 二分法查找元素及其索引

参考:
lower_bound
equal_range
binary_search

本文主要提到四个库函数都来至algorithm头文件,分别是 lower_bound,upper_bound,binary_search,equal_range.
既然要用二分法查元素,那当然前提是查的容器内容是有序的.

---

lower_bound

返回值:指向第一个不小于给定值的元素的迭代器
定义如下:

default (1) 
template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);
custom (2)  
template <class ForwardIterator, class T, class Compare>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

---

upper_bound

返回值:返回指向第一个大于给定值的元素的迭代器
定义和lower_bound差不多,不贴了

---

binary_search

返回值:bool类型,判断一个元素是否在区间内
定义如下:

default (1) 
template <class ForwardIterator, class T>
bool binary_search (ForwardIterator first, ForwardIterator last,
const T& val);
custom (2)  
template <class ForwardIterator, class T, class Compare>
bool binary_search (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);

---

equal_range

其实这个就是上面那两个的结合体,用std::pair结合的.
返回值:匹配特定键值的元素区间
定义如下:

default (1) 
template <class ForwardIterator, class T>
  pair<ForwardIterator,ForwardIterator>
    equal_range (ForwardIterator first, ForwardIterator last, const T& val);
custom (2)  
template <class ForwardIterator, class T, class Compare>
  pair<ForwardIterator,ForwardIterator>
    equal_range (ForwardIterator first, ForwardIterator last, const T& val,
Compare comp);

---

下面就是找元素了

以下代码在命名空间std内

初始化一下先:

    //有序列
vector<int> vec = { 0,2,5,5,5,8,10,18,26,30 };
//要查找的元素,这里举例为5
int val = 5;    

方法1:

    //该元素所在范围
vector<int>::iterator low, up;

    low = lower_bound(vec.begin(), vec.end(), val);
//这里指向第一个5
    up = upper_bound(vec.begin(), vec.end(), val);
//这里指向最后一个5的后一个数,也就是8

//判断low是否已经到了结尾,若是说明找不到且大于前面的值,
//然后判断low所指向的值是否等于要查的值即可.
if (low != vec.end() && *low == val)
cout << "found it! " << endl;

cout << "lower_bound at position " << (low - vec.begin()) << endl;
cout << "upper_bound at position " << (up - vec.begin()) << endl;

方法2:

    //auto实际上就是pair<vector<int>,vector<int>>
    auto bounds = equal_range(vec.begin(), vec.end(), val);
//判断同方法一
if (bounds.first != vec.end() && *bounds.first == val)
        cout << "found it! " << endl;

    cout << "bound at position " << (bounds.first - vec.begin()) << " and " << (bounds.second - vec.begin()) << endl;

如果只要判断元素是否在容器里,用binary_search就好了

    bool findIt = binary_search(vec.begin(), vec.end(), val);
if (findIt)
        cout << "binary_search found " << val << endl;
else
        cout << "binary_search not found " << val << endl;

运行结果:

---

**cstdlib库里面有个bsearch函数,也是二分查找,但用法比较复杂,有兴趣可以自己去看看.