二分检索(分治)

2012/09/21

分治二分检索
基本思路:1 ,2 ,3 ,4 ,5,6 ,7,8,9在这9个元素中(有序数组)，请检索元素5，是否在这9个元素中，如果利用普通的循环的话如果这堆元素有很大，比如说10000000个元素，计算机肯定会超时！利用分治的思想可以很好的解决这个问题！

示例:
6个元素数组(23 34 46 768 343 343)，检索给出的4个数(2 4 23 343)是否在数组中,是的话输出YES，否则NO
[cpp]
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
long long *p,*q,i;
int m,n,t;cin>>m>>n;
p=new long long[m];
q=new long long[n];
for(i=0;i<m;i++) cin>>p[i];
sort(p,p+m);
long long low,high,mid;
for(i=0;i<n;i++)
{
low=0,high=m-1;
t=0;cin>>q[i];
while(low<=high)
{
mid=(low+high)/2; //代码核心部分 low为上界,high为下界,mid为中间标记
if(p[mid]>q[i]) high=mid-1;//如果元素比待检索元素大,缩小下界范围
else if(p[mid]<q[i]) low=mid+1;//如果元素比待检索元素小,缩小上界范围
else {t=1;break;}
}
if(t) cout<<“YES”<<endl;
else cout<<“NO”<<endl;
}
delete[] p,q;
return 0;
}
[/cpp]

Blogroll