二分查找模板 nyoj626

ゝ一纸荒年。 2022-03-18 03:12 188阅读 0赞

题意就是给你两串数组，找其中相同数字的个数，二分查找模板题，可以有其他简单方法：

切记在二分浮点数的时候是比较两个数的接近程度而不是直接比较大小，即abs(l-r)>=1e-10

还有e^x的写法是exp(x);

贴二分查找代码：

#include <iostream>
    #include <stdio.h>
    #include <algorithm>
    using namespace std;
    int a[50010],b[50010];
    bool search(int x,int *p,int len)  //二分查找
    {
        int left=0,right=len-1;
        while(left<=right)   //注意这里必须等于
        {
            int mid=(left+right)/2;
            if(x>p[mid])
                left=mid+1;
            else if(x==p[mid])
                {
                    return true;
                }
            else
                right=mid-1;
        }
        return false;
    }
    int main()
    {
        int m,n,count;
        while(~scanf("%d%d",&m,&n))
        {
            count=0;
            if(n==0&&m==0) break;
            for(int i=0;i<m;i++)
                scanf("%d",&a[i]);
            for(int i=0;i<n;i++)
                scanf("%d",&b[i]);
            if(m>=n)
            {
                sort(a,a+m);
                for(int i=0;i<n;i++)
                {
                    if(search(b[i],a,m))
                        count++;
                }
                printf("%d\n",count);
            }
            else
            {
                sort(b,b+n);
                for(int i=0;i<m;i++)
                {
                    if(search(a[i],b,n))
                        count++;
                }
                printf("%d\n",count);
            }
        }
    
        return 0;
    }
    /*
    8 9
    1 5 6 9 10 12 16 59
    5 6 9 8 15 17 65 98 105
    */

数组下标法：

#include <stdio.h>
    #include <string.h>
    
    bool in[100002];
    
    int main()
    {
        int m,n,num;
        while(~scanf("%d%d",&m,&n))
        {
            int ans = 0;
            memset(in,0,sizeof(in));
            while(m--)
            {
                scanf("%d",&num);
                in[num] = true;
            }
            while(n--)
            {
                scanf("%d",&num);
                if(in[num])
                    ans++;
            }
            printf("%d\n",ans);
        }
    	return 0;
    }