HDU-3763-CD（二分）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3763

题目大意：a和b分别有一些光盘，他们每个人对于每种光盘只有一个，他们准备卖出去他们共同拥有的光盘，问最多能卖多少

题解：便利一个二分一个O(nlogn)

符合二分总结中的第一种情况   1.对于查找目标值的二分查找

ac：

//#pragma comment(linker, "/STACK:1024000000,1024000000") 
 
#include<stdio.h>
#include<string.h>  
#include<math.h>  
  
#include<map>   
//#include<set>
#include<deque>  
#include<queue>  
#include<stack>  
#include<bitset> 
#include<string>  
#include<fstream>
#include<iostream>  
#include<algorithm>  
using namespace std;  
 
#define ll long long  
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b) 
#define clean(a,b) memset(a,b,sizeof(a))// 水印 
//std::ios::sync_with_stdio(false);
const int MAXN=1e6+10;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;
const double PI=acos(-1.0);

int a[MAXN],b[MAXN];
int n,m;

int main()
{
	//std::ios::sync_with_stdio(false);
	while(scanf("%d%d",&n,&m))
	{
		if(n==0&&m==0)
			break;
		for(int i=1;i<=n;++i)
			scanf("%d",&a[i]);
		for(int i=1;i<=m;++i)
			scanf("%d",&b[i]);
		int ans=0;
		for(int i=1;i<=n;++i)
		{
			int l=1,r=m,mid;
			while(l<=r)
			{
				mid=(l+r)>>1;
				if(a[i]==b[mid])
				{
					ans++;
					break;
				}
				else if(b[mid]<a[i])//mid在key左边 
					l=mid+1;
				else
					r=mid-1;
			}
		}
		printf("%d\n",ans);
	}
}