3376 数据结构实验之查找四：二分查找

偏执的太偏执、 2022-07-14 13:42 122阅读 0赞

[数据结构实验之查找四：二分查找][Link 1]

#include <bits/stdc++.h>  
    using namespace std;  
    const int maxn = 1e6+10;  
    int a[maxn];  
    
    int main()  
    {  
        int n,m;  
        scanf("%d%d",&n,&m);  
        for(int i=0; i<n; i++)  
            scanf("%d",&a[i]);  
        while(m--)  
        {  
            int x;  
            scanf("%d",&x);  
            int t = lower_bound(a, a + n, x) - a;  
            if(a[t] == x)  
                printf("%d\n",t);  
            else  
                printf("-1\n");  
        }  
        return 0;  
    }

#include<stdio.h>  
    int flag;  
    int data[1000001];  
    int find(int low,int high,int key)  
    {  
        int mid=(high-low)/2+low;  
        if(low<=high)//要计算好下标  
        {  
            if(data[mid]==key)  
            {  
                flag=1;  
                return mid;  
            }  
            else if(data[mid]>key)  
                return find(low,mid-1,key);  
            else if(data[mid]<key)  
                return find(mid+1,high,key);  
        }  
    }  
    int main()  
    {  
        int n,m,i,key;  
        scanf("%d%d",&n,&m);  
        for(i=0; i<n; i++)  
            scanf("%d",&data[i]);  
        for(i=1; i<=m; i++)  
        {  
            flag=0;  
            scanf("%d",&key);  
            int t=find(0,n-1,key);  
            if(flag)  
                printf("%d\n",t);  
            else  
                printf("-1\n");  
        }  
    }

用C++写则为超时代码，加入 std::ios\_base::sync\_with\_stdio(false)和 std::cin.tie(0)可加快cin、cout，即可AC;

[Link 1]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/1908/pid/3376