42. 이분검색

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main()
{
    freopen("input.txt", "rt", stdin);

    int n, m, lt, rt, i, mid, tmp;

    scanf("%d %d", &n, &m);

    vector<int> a;

    for (i = 0; i < n; i++)
    {
        scanf("%d", &tmp);
        a.push_back(tmp);
    }
    sort(a.begin(), a.end());

    lt = 0;
    rt = n - 1;

    while (lt <= rt)
    {

        mid = (lt + rt) / 2;

        if (a[mid] == m)
        {
            break;
        }
        else if (a[mid] > m)
        {
            rt = mid - 1;
        }
        else
            lt = mid + 1;
    }
    printf("%d ", a[mid]);

    return 0;
}

 

정렬된 배열에서 범위의 양 끝을 가리키는 lt, rt 변수와 범위의 중간을 가리키는 mid 변수를 사용하여 a[mid]값과 m값(key값)을 비교하여 검색하는 알고리즘이다.