[이진탐색] 1920 수 찾기, Binary search

 

Binary search는

 

'정렬된 배열'에서 특정 원소를 찾을 때,

 

O(logN)의 탐색시간을 보장합니다.

 

 

따라서, O(N)만큼 걸리는 Linear search 보다는 성능이 좋을 수 있습니다.

 

처음에는 재귀함수로 구현하였고,

이와 거의 비슷하게 반복문으로 구현할 수 있었습니다.

 

#include <cstdio>
#include <algorithm>

int a[100001];

// array는 정렬되어 있어야 함.
int binarySearch(int first, int last, int k){
    int mid = (first + last) / 2;
    if (first > last) return -1;
    else {
        if (a[mid] == k) return mid;
        else {
            if (a[mid] < k){
                binarySearch(mid + 1, last, k);
            }
            else{
                binarySearch(first, mid - 1, k);
            }
        }
    }

}

// 반복문이 조금 더 빠르다. 
int binarySearchIter(int length, int key){
    int first = 0;
    int last = length - 1;

    while(first <= last){
        int mid = (first + last) / 2;
        if (a[mid] == key) return mid;
        else {
            if (a[mid] < key){
                first = mid + 1;
            }
            else {
                last = mid - 1;
            }
        }
    }
    return -1;
}

int main() {
    int n, m, k;
    scanf("%d", &n);
    for (int i=0; i<n; i++){
        scanf("%d", &a[i]);
    }
    std::sort(a, a + n);

    scanf("%d", &m);
    for (int i=0; i<m; i++){
        scanf("%d", &k);
        if (binarySearchIter(n, k) == -1) printf("0\n");
        else printf("1\n");
    }


    return 0;
}