이분탐색 (Binary search)

이분탐색의 경우에는 

 - 정렬되어진 리스트에서 어떤값을 빠르게 찾는 알고리즘으로서 

 - 리스트 혹은 배열의 크기를 N 이라고 했을 때 찾는데 logN 의 시간이 걸린다.

이런식으로 작동이 되며

Left가 Right 보다 클 때 까지 계속적으로 반복을한다. 

시간복잡도가 logN인 이유가 바로 절반으로 계속 나누어 주기 때문이다.

참고 코드는 

while (left <= right) {

    int mid = (left + right) / 2;

    if (a[mid] == x) {

        position = mid;

        break;

    } else if (a[mid] > x) {

        right = mid-1;

    } else {

        left = mid+1;

    }

}

을 참고하면 될 것이다.

그런데 분명 이렇게 구현을 하다보면 까먹을 경우도 발생 할 것이다. 그렇다면 우리는 어떻게 해야할까 ... 바로 STL을 쓰는게 가장 간편 !!

while (m--) {

    int num;

    scanf("%d",&num);

    printf("%d ",binary_search(a,a+n,num));

}

이런식으로 구현을 한다면 binary_search의 반환값이 있으면 1이고 없으면 0인것을 기억하고 사용하면 될 것이다.