C language ALDS1_4_B Binary Search

problem

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=ja

code

#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;
}

point

--Can only be used when the data keys are aligned

Impressions

――I was doing something else on the way. I have to use screen time.

Time required: 30 minutes

Recommended Posts

C language ALDS1_4_B Binary Search
[C language algorithm] Binary search tree
C language ALDS1_3_B Queue
Binary search in Python / C ++
C language ALDS1_4_A Linear Search
Algorithm in Python (ABC 146 C Binary Search
visualize binary search
ABC146C (binary search)
Binary search in Python
Binary search (python2.7) memo
[Python] Binary search ABC155D
Binary search with python
Binary search with Python3
[C language algorithm] Endianness
Binary search in Python (binary search)
[C language algorithm] Block movement
Heapsort made in C language
Algorithm in Python (binary search)
[C language] readdir () vs readdir_r ()
Write a binary search in Python
Multi-instance module test in C language
Function pointer and objdump ~ C language ~
Realize interface class in C language
Writing C language with Sympy (metaprogramming)
High energy efficiency programming language C
Introduction to Protobuf-c (C language ⇔ Python)
Binary search summary for competition professionals
C language 8 queens problem solving 3 patterns
Segfault with 16 characters in C language
Call c language from python (python.h)
AtCoder ABC172 C Cumulative Sum Binary Search Solved by Ruby and Python