알고리즘 - 이분탐색 - c++

이 코드를 쉽게 이해하기 위해서 그림을 그려보았다

 

이 그림을 이해하면 이분탐색을 이해할 수 있다.

이 그림만 봐도 충분히 이해가 될것이라고 생각하지만 더욱 확실한 이해를 위해 주석으로 예제를 넣어보았다

 

#include <iostream>
#include <algorithm>
using namespace std;

int a[100000];

int main() {
    int n;
    cin >> n;                         // 10 10개를 입혁한다는뜻
    for (int i = 0; i < n; ++i)
        cin >> a[i];                  // 6 3 2 10 10 10 -10 -10 7 3 배열이다

    sort(a, a + n);                   // -10 -10 2 3 3 6 7 10 10 10 정렬을 해준것이다

    int m;
    cin >> m;                         // 8 8개를 입력한다는 뜻
    for (int i = 0; i < m; ++i) {
        int x;
        cin >> x;                     // 10 9 -5 2 3 4 5 -10 배열이다

        int left = 0, right = n - 1;
        bool found = false;

        while (left <= right) {
            int mid = (left + right) / 2; //mid를 만들어준다(mid가 핵심이다)
            if (a[mid] == x) {            // 만약 x면? found == true 인거다
                found = true;            // 뒤에 나올 if문에서 true 이거나 아닌게 필요
                break;
            } else if (a[mid] < x) {      //만약 크다면 left의 값이 이동하고
                left = mid + 1;
            } else {                     //작다면 right의 값이 이동한다
                right = mid - 1;
            }
        }

        if (found) {
            cout << 1 << '\n';     //아까 mid가 x면 found = ture 해줬던걸 사용하는것
        } else {
            cout << 0 << '\n';
        }
    }

    return 0;
}