A-A+

二分检索(分治)

2012年09月21日 分治 暂无评论 阅读 61 次

分治二分检索
基本思路: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]

标签:

给我留言

Copyright © C/C++程序员之家 保留所有权利.   Theme  Ality 浙ICP备15011757号-3

用户登录