（10）STL算法之搜索（二） 二分查找
之前在（3）STL算法之搜索里边介绍过几个查找函数，如find()、search()，这些函数的底层实现的都是顺序查找，采用的是遍历的方式，在某些时候效率并不高，例如当指定区域里的数据处于有序状态时，查找某个目标值，显示二分查找的效率更高。然后我是昨天写算法题的时候才看到别人用到了STL算法里的lower_bound()。才了解到了lower_bound()等其他几个底层为二分查找的查找函数。先来看下我遇到的那道题。
问题：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。
题目来源：LeeCode 35 搜索插入位置
下面的答案是采用二分查找的解法。自从发现STL提供的二分查找算法，我就不喜欢这种写法了，哈哈哈哈。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = n - 1, ans = n;
while (left <= right) {
int mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
};再来看看用轮子的写法...，看着简直太舒服了
int searchInsert(vector<int>& nums, int target)
{
return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
}接下来介绍这四个基于二分查找的算法。
二分查找：二分查找是一种效率较高的查找方法。但二分查找有一定的条件限制：要求线性表必须采用顺序存储结构，且表中元素必须按关键字有序（升序或降序均可）。在有序表中，取中间的记录作为比较对象，如果要查找记录的关键字等于中间记录的关键字，则查找成功；若要查找记录的关键字大于中间记录的关键字，则在中间记录的右半区继续查找。不断重述上述查找过程，直到查找成功，或有序表中没有所要查找的记录，查找失败。
// 代码描述
template <class ElemType, class KeyType>
int BinSerach(ElemType elem[], int n, KeyType key)
{ // 操作结果: 在有序表中查找其关键字的值等于key的记录,如查找成功,则返回此记录的序号,否则返回-1
int low = 0, high = n - 1; // 区间初值
while (low <= high)
{
int mid = (low + high) / 2; // 区间中间位置
if (key == elem[mid])
return mid; // 查找成功
else if (key < elem[mid])
high = mid - 1; // 继续在左半区间进行查找
else
low = mid + 1; // 继续在右半区间进行查找
}
return -1; // 查找失败
}一、lower_bound() & upper_bound()
lower_bound()算法可以在参数一和参数二指定的范围内查找不小于参数三的第一个元素，即大于等于参数三的第一个元素。前两个参数必须是正向迭代器.
// 声明与定义
template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,const T& val);
template <class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,const T& val, Compare comp);
comp是自定义规则，用于查找区域内第一个不符合comp规则的元素
template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val)
{
ForwardIterator it;
iterator_traits<ForwardIterator>::difference_type count, step;
count = distance(first, last);
while (count > 0)
{
it = first;
step = count / 2;
advance(it, step); // it迭代器移动到step位置
if (*it < val) // if (comp(*it,val)) version 2
{
first = ++it; // 首地址变为中间地址的下一个地址
count -= step + 1; // 求出从剩下的元素个数
}
else
count = step;
}
return first;
}upper_bound()算法用于在参数一和参数二指定的范围内查找大于参数三的第一个元素，
template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);
template <class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
ForwardIterator it;
iterator_traits<ForwardIterator>::difference_type count, step;
count = std::distance(first,last);
while (count>0)
{
it = first; step=count/2; std::advance (it,step);
if (!(val<*it)) // or: if (!comp(val,*it)) version (2)
{
first=++it; count-=step+1;
}
else
count=step;
}
return first;
}
用法示例：
#include <iostream>
#include <algorithm> // std::lower_bound, std::upper_bound, std::sort
#include <vector>
int main() {
int arr[] = { 10,20,30,30,20,10,10,20 };
std::vector<int> v(arr, arr + 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, upp;
low = std::lower_bound(v.begin(), v.end(), 20); // 查找返回 >=20 的第一个数的位置
upp = std::upper_bound(v.begin(), v.end(), 20); // 查找返回 >20 的第一个数的位置 ^
std::cout << "lower_bound at position " << (low - v.begin()) << '\n';
std::cout << "upper_bound at position " << (upp - v.begin()) << '\n';
return 0;
}#include <iostream>
#include <algorithm> // std::lower_bound
#include <vector>
using namespace std;
bool mycomp(int it, int val) //普通函数 定义查找规则
{
return it > val;
}
class mycomp2 //以函数对象的形式定义查找规则
{
public:
bool operator()(const int& it, const int& val)
{
return it > val;
}
};
int main() {
int a[5] = { 1,2,3,4,5 };
//从 a 数组中找到第一个不小于 3 的元素
int* p = lower_bound(a, a + 5, 3);
cout << "*p = " << *p << endl;
vector<int> myvector{ 4,5,3,1,2 };
//根据 mycomp2 规则，从 myvector 容器中找到第一个违背 mycomp2 规则的元素
vector<int>::iterator iter = lower_bound(myvector.begin(), myvector.end(), 3, mycomp2());// 这里的3作为自定义规则的参数二
cout << "*iter = " << *iter;
return 0;
}此例程来源： http://c.biancheng.net/view/7521.html
// 晚上再写，现在要去干饭了。
二、binary_search()
在指定范围内查找是否存在某元素。
函数实现
template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& val);
template <class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& val)
{
first = std::lower_bound(first, last, val);
return (first != last && !(val < *first));
//调用的是lower_bound，第一行返回第1个与查找值相等的迭代器并赋值给first，
//若不存在则first为第1个大于查找值的迭代器。 first还未指向last，且 val < *first 为假，则说明存在val
}
template <class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& val, Compare comp)
{
first = std::lower_bound(first, last, val, comp);
return (!(first == last) && !(comp(val, *first)));
}
用法示例：
#include <iostream>
#include <algorithm>
#include <vector>
bool myfunction(int val, int it)
{
return (val < it);
}
int main() {
int arr[] = { 1,2,3,4,5,4,3,2,1 };
std::vector<int> v(arr, arr + 9); // 1 2 3 4 5 4 3 2 1
std::sort(v.begin(), v.end());
std::cout << "search elem 3 ";
if (std::binary_search(v.begin(), v.end(), 3))
std::cout << "found!\n";
else
std::cout << "not found.\n";
std::sort(v.begin(), v.end(), myfunction);
std::cout << "search elem 6 ";
if (std::binary_search(v.begin(), v.end(), 6, myfunction))
std::cout << "found!\n";
else
std::cout << "not found.\n";
return 0;
}三、equal_range()
用于在指定范围【first，last）内查找等于目标值的所有元素
template <class ForwardIterator, class T> pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& val);
template <class ForwardIterator, class T, class Compare> pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
template <class ForwardIterator, class T> pair<ForwardIterator,ForwardIterator>
equal_range (ForwardIterator first, ForwardIterator last, const T& val)
{
ForwardIterator it = std::lower_bound (first,last,val);
return std::make_pair ( it, std::upper_bound(it,last,val) );
// 该函数会返回一个pair类型，包括两个正向迭代器，第一个迭代器指向【first，last）中第一个等于val的值
//第二个迭代器执行第一个【first，last）中第一个大于val的值,如果有自定义规则，就按自定义规则执行，如下边的例程。
}
// version (2)
template <class ForwardIterator, class T> pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& val)
{
ForwardIterator it = std::lower_bound(first, last, val, comp);
return std::make_pair(it, std::upper_bound(it, last, val, comp));
}用法示例：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool comp(int i, int j)
{
return (i > j);
}
int main()
{
vector<int> v{ 10, 20, 30, 30, 20, 10, 10, 20 };
pair<vector<int>::iterator, vector<int>::iterator> bounds;
sort(v.begin(), v.end());
for (int val : v)
cout << val << " ";
cout << endl;
bounds = equal_range(v.begin(), v.end(), 20);
cout << (bounds.first - v.begin()) << " and " << (bounds.second - v.begin()) << endl;
sort(v.begin(), v.end(), comp);
for (int val : v)
cout << val << " ";
cout << endl;
bounds = equal_range(v.begin(), v.end(), 20, comp);
cout << (bounds.first - v.begin()) << " and " << (bounds.second - v.begin()) << endl;
}
/*
10 10 10 20 20 20 30 30
3 and 6
30 30 20 20 20 10 10 10
2 and 5
*/