查找相关算法

STL中提供了丰富的查找算法函数，使用时要注意一些函数的特殊条件，例如二分查找binary_search就要求查找的区间的元素是有序排列的。同样地，涉及到区间时，一般是左闭右开。

一、计数count、count_if

count函数在指定区间（左闭右开）顺序比较每个元素与目标值，统计与目标值相等的元素的数量，使用方法：count(begin,end,x);。如果元素类型是结构体（或者类），需要重载用于判断相等的==运算符。

此外还有count_if函数，指定一个判断函数（返回值为bool）作为count_if函数的参数， 在指定区间顺序判断每个元素，统计符合条件的元素（元素作为参数调用判断函数返回值为true）的次数，使用方法：count_if(begin,end,function);。

#include<iostream>
#include<algorithm>
using namespace std;
//判断偶数 
bool even(const int &n){
	return n%2==0;
}
int main()
{
	const int N = 6;
	int a[N] = {3,2,4,5,1,3};
	cout<<count(a,a+N,3)<<endl;
	cout<<count_if(a,a+N,even)<<endl; 
    return 0;
}

二、顺序查找find、find_if

find函数用来在指定区间（左闭右开）顺序查找目标值，如果找到，返回指向第一个目标值的指针（或迭代器），没有找到返回区间右边界，使用方法：find(begin,end,x);。 如果元素类型是结构体（或者类），需要重载用于判断相等的==运算符。

此外还有find_if函数用来在指定区间（左闭右开）顺序查找符合条件的第一个元素，使用方法：find(begin,end,function);。

#include<iostream>
#include<algorithm>
using namespace std;
//判断奇数 
bool odd(const int &n){
    return n%2!=0;
}
int main()
{
    const int N = 6;
    int x = 3;
    int a[N] = {3,2,4,5,1,3};
    
    int *p = find(a,a+N,x);
    if(p!=a+N){
        cout<<"found "<<x<<" at a["<<(p-a)<<"]"<<endl;
    }
    
    //使用循环找到所有目标值
    int *q = find(a,a+N,x);
    while(q!=a+N){
        cout<<"found "<<x<<" at a["<<(q-a)<<"]"<<endl;
        q = find(q+1,a+N,x);
    }
    
    p = find_if(a,a+N,odd);
    if(p!=a+N){
        cout<<"found odd "<<*p<<" at a["<<(p-a)<<"]"<<endl;
    }
    
    //使用循环找到所有满足条件的元素
	int *r = find_if(a,a+N,odd); 
    while(r!=a+N){
        cout<<"found odd "<<*r<<" at a["<<(r-a)<<"]"<<endl;
        r = find_if(r+1,a+N,odd);
    }
    
    return 0;
}

三、连续出现n次x：search_n

search_n函数用法：search_n(begin,end,n,x);，在\([begin,end)\)区间内查找连续出现\(n\)次\(x\)的情况，返回符合情况的第一个\(x\)的位置。

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    const int N = 10;
    int a[N] = {4,4,2,5,4,4,4,4,4,6};
    
    int *p = search_n(a,a+N,3,4);
    if(p!=a+N){
    	cout<<"第一次连续3个4出现在 a["<<p-a<<"]"<<endl;
	}    
    cout<<endl;
    
    int *q = search_n(a,a+N,3,4);
    int cnt = 0;
    while(q!=a+N){
    	cout<<"第"<<(++cnt)<<"次连续3个4出现在 a["<<q-a<<"]"<<endl;
    	q = search_n(q+1,a+N,3,4);
	}
    return 0;
}

四、find_first_of

find_first_of函数用法：find_first_of(begin1,end1,begin2,end2);，在\([begin1,end1)\)区间内查找\([begin2,end2)\)区间的任意一个元素第一次出现的位置。

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	const int N = 6,M = 3;
	int a[N] = {1,2,3,4,5,6};
	int b[M] = {5,1,3};
	
	int *p = find_first_of(a,a+N,b,b+M);
	if(p!=a+N) cout<<*p<<endl;
	
	//使用while循环找出所有元素 
	int *q = find_first_of(a,a+N,b,b+M);
	while(q!=a+N){
		cout<<*q<<endl;
		q = find_first_of(q+1,a+N,b,b+M);
	}
    return 0;
}

五、子序列查找search/find_end

search函数用法：search(begin1,end1,begin2,end2);，在\([begin1,end1)\)区间内查找\([begin2,end2)\)区间的所有元素依次出现的情况（此时\([begin2,end2)\)序列称为\([begin1,end1)\)序列的子序列），返回第一次符合情况的位置。find_end函数用法和search函数一致，不过find_end函数是逆序查找。

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    const int N = 10,M = 3;
    int cnt = 0;
    int a[N] = {1,2,3,4,5,1,2,3,4,5};
	int b[M] = {2,3,4};
	
	//正向查找子序列 
	int *p = search(a,a+N,b,b+M);
	if(p!=a+N){
		cout<<"数组b是数组a的子序列"<<endl;
		cout<<"数组b中的元素依次完整出现第一次在数组a的a["<<p-a<<"]处"<<endl;
	}
	
	cout<<endl;
	//正向查找所有子序列
	cnt = 0; 
	p = search(a,a+N,b,b+M);
	while(p!=a+N){
		cout<<"数组b中的元素依次完整出现第【"<<(++cnt)<<"】次在数组a的a["<<p-a<<"]处"<<endl;
		p = search(p+1,a+N,b,b+M);
	}
	
	cout<<endl;
	//反向查找子序列 
	int *q = find_end(a,a+N,b,b+M);
	if(q!=a+N){
		cout<<"数组b是数组a的子序列"<<endl;
		cout<<"数组b中的元素依次完整出现最后一次在数组a的a["<<q-a<<"]处"<<endl;
	}
	
	cout<<endl;
	//反向查找所有子序列
	cnt = 0;
	int *end = a+N;
	q = find_end(a,end,b,b+M);
	while(q!=end){
		end = q;
		cout<<"数组b中的元素依次完整出现第【"<<(++cnt)<<"】次在数组a的a["<<q-a<<"]处"<<endl;
		q = search(a,end,b,b+M);
	}
    return 0;
}

这两个函数还可以有第5个参数，是一个bool类型的函数，用来指定判断两个序列对应位置的两个元素“相等”的规则：

#include<iostream>
#include<algorithm>
using namespace std;
bool judge(const int &x,const int &y){
	return abs(x)==abs(y);
}
int main()
{
    const int N = 10,M = 3;
    int a[N] = {1,-2,3,-4,5,1,2,-3,-4,5};
	int b[M] = {2,-3,4};
	
	//正向查找子序列 
	int *p = search(a,a+N,b,b+M,judge);
	if(p!=a+N){
		cout<<"数组b是数组a的子序列"<<endl;
		cout<<"数组b中的元素依次完整出现第一次在数组a的a["<<p-a<<"]处"<<endl;
	}
	
	cout<<endl;
	//反向查找子序列 
	int *q = find_end(a,a+N,b,b+M,judge);
	if(q!=a+N){
		cout<<"数组b是数组a的子序列"<<endl;
		cout<<"数组b中的元素依次完整出现最后一次在数组a的a["<<q-a<<"]处"<<endl;
	}
    return 0;
}

六、二分查找binary_search

binary_search函数使用二分查找的方式，判断在一个已经有序的区间内某个元素是否存在，如果存在，返回值为true，否则返回值是false。使用方式： binary_search(begin,end,x);，还可以指定第4个参数（一个比较函数）。特别注意的是：调用binary_search函数时，要确保查找的区间有序（默认处理升序情况，可以通过比较函数处理其它排序情况），否则返回结果不可靠。

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	const int N = 5;
    int a[N] ={1,2,3,4,5};
    int x = 4;
    //binary_search查找时默认容器元素升序排列，这里数组a元素升序排列 
	if(binary_search(a,a+N,x)) cout<<"Found "<<x<<endl;
	else cout<<"Not found "<<x<<endl;
	
	int b[N] = {5,4,3,2,1};
	//binary_search查找时默认容器元素升序排列，这里数组b元素降序排列（要避免这样的情况） 
	if(binary_search(b,b+N,x)) cout<<"Found "<<x<<endl;
	else cout<<"Not found "<<x<<endl;
	
	//还可以通过比较函数指定二分查找时比较规则 
	if(binary_search(b,b+N,x,greater<int>())) cout<<"Found "<<x<<endl;
	else cout<<"Not found "<<x<<endl;
    return 0;
}

七、lower_bound/upper_bound和equal_range

lower_bound函数用于在指定区间（默认认为区间升序排列）查找不小于目标值的第一个元素。也就是说，使用该函数在指定范围内查找某个目标值时，最终查找到的不一定是和目标值相等的元素，还可能是比目标值大的元素。使用方法：lower_bound(begin,end,x);

upper_bound函数用于在指定区间（默认认为区间升序排列） 查找大于目标值的第一个元素，使用方法和lower_bound相同。

需要注意的是lower_bound和upper_bound都是使用了二分查找的方式，所以和binary_search一样，适用于已经有序的区间。

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    const int N = 6;
    int a[N] ={1,2,3,3,4,5};
    
    //要查找的目标值 
    int x = 3;
    
    int *p = lower_bound(a,a+N,x);
    if(p!=a+N){
        cout<<*p<<endl;        //如果a[0]>=x，此时lower_bound返回值p==a
        //[a,p)区间元素均小于x，a[p]可能等于x，也可能大于x
        for(int *t=a;t!=p;t++) cout<<*t<<" ";
        cout<<endl;
    } 
    
    int *q = upper_bound(a,a+N,x);
    if(q!=a+N){
        cout<<*q<<endl;
        //[q,a+N)区间元素均大于x
        for(int *t=q;t!=a+N;t++) cout<<*t<<" ";
        cout<<endl;
    } 
    
    //第一个不小于x的元素位置在：p
	//第一个大于x的元素位置在：q
	//如果数组中有元素x，那么肯定有：q>p
	//此时[p,q)的元素值都是x 
	if(q>p){
		while(p!=q){
			cout<<*p<<" ";
			p++;
		}
	}
    return 0;
}

equal_range函数的用法和lower_bound/upper_bound相同，其返回值是一个pair，pair的first成员是lower_bound函数处理结果，pair的second成员是upper_bound函数的处理结果：

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    const int N = 8;
    int a[N] ={1,2,3,3,3,3,4,6};
    
    int x = 3;
    pair<int*,int*> ans = equal_range(a,a+N,x);
    //第一个不小于x的元素位置在：ans.first
	//第一个大于x的元素位置在：ans.second
	//如果数组中有元素x，那么肯定有：ans.second>ans.first
	//此时[ans.first,ans.second)的元素值都是x 
	if(ans.second>ans.first){
		int *p = ans.first;
		while(p!=ans.second){
			cout<<*p<<" ";
			p++;
		}
	}
    return 0;
}

三个函数也可以指定一个比较函数作为第4个参数用来设置二分查找时比较规则。如果要在一个降序区间查找不大于目标值的第一个元素或者小于目标值的第一个元素，也可以使用这三个函数，不过第4个参数需要使用greater()<T>()：

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	const int N = 6;
    int a[N] ={5,4,3,3,2,1};
    
    //要查找的目标值 
    int x = 3;
    
    int *p = lower_bound(a,a+N,x,greater<int>());
    if(p!=a+N){
    	cout<<*p<<endl;		//如果a[0]<=x，此时lower_bound返回值p==a
    	//[a,p)区间元素均大于x，a[p]可能等于x，也可能小于x
		for(int *q=a;q!=p;q++) cout<<*q<<" ";
		cout<<endl;
	}
    
    p = upper_bound(a,a+N,x,greater<int>());
    if(p!=a+N){
    	cout<<*p<<endl;
    	//[p,a+N)区间元素均小于x
    	for(int *q=p;q!=a+N;q++) cout<<*q<<" ";
		cout<<endl;
	} 
    
    return 0;
}