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

2019-11-08 20:05:23

字體：大中小

來源：轉載

供稿：網友

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;

運行結果: 這里寫圖片描述