Recherche binaire ALDS1_4_B langage C

#include <stdio.h>

int A[1000000],N;

int binary_search(int key){
    int left = 0;
    int right = N;
    int mid;

    while(left < right){
        mid = (left + right) / 2;
        if (key == A[mid])
            return 1;
        if (key > A[mid])
            left = mid + 1;
        else if (key < A[mid])
            right = mid;
    }
    return 0;
}

int main(void)
{
    int i, q, key, count = 0;
    
    scanf("%d", &N);
    for(i = 0; i < N; i++)
        scanf("%d", &A[i]);

    scanf("%d", &q);
    for(i = 0; i < q; i++){
        scanf("%d", &key);
        if (binary_search(key))
            count++;
    }
    printf("%d\n", count);

    return 0;
}

Recommended Posts