이진탐색(Binary Search)

1. 이진탐색(Binary Search)

1.1. 이진탐색 이란?

'Up and Down'이라는 게임이 있습니다. 사회자는 일정 범위의 수 'x'를 생각한다. 참가자가 어떤숫자 'a'를 말했을때, 'a'가 'x' 보다 작으면 사회자는 'Up'이라고 말하며 'a'가 'x'보다 크면 'Down'이라고 말을 합니다. 그렇다면 가장 빠르게 'x'를 찾는 방법은 무엇일까요? 이에 대한 해답은 해당 범위의 중간값을 말하면서 'x'의 범위를 좁혀나가는 방법입니다.

이러한 방법으로 탐색을 해 나가는 것을 이진탐색이라고 합니다. 이진 탐색을 위해서는 우선 정렬이 되어있어야 한다는 조건이 있지만, 매우 큰 범위내에서 빠르게 찾고싶은 데이터를 찾을 수 있는 장점이 있습니다. 결과적으로 이진탐색은 O(logN) 라는 시간복잡도를 나타냅니다.

1.2. 이진탐색의 탐색과정

아래는 정렬된 10개의 수 1, 3, 4, 6, 9, 10, 11, 13, 15, 19에서 11의 위치를 찾는 과정입니다.

 

우선 처음엔 수의 가장 왼쪽 순번인 1을 left에 가장 오른쪽 순번인 10을 right로 저장하고 이에대한 중앙값인 5를 middle로 정합니다.

middle이 위치한 값인 9는 찾고싶은 수인 11보다 더 작기 때문에 더 큰범위를 탐색해야 합니다.

따라서 left는 middle의 위치에 1을 더한 6으로 변경하고 right는 10으로 유지합니다.

left와 right의 중앙값인 middle은 8로 변경 합니다.

middle이 가리키는 수인 13은 찾고자하는 11보다 크기 때문에 이번에는 작은 범위를 탐색해야 합니다.

이를 위해 right의 위치는 middle의 위치보다 1이 작은 7로 이동하며, left는 6으로 그대로 유지합니다.

새롭게 설정된 left와 right의 중앙값인 middle은 6이 됩니다.

middle이 가리키는 수는 10으로 찾고싶은 수인 11보다 작으므로 탐색 범위를 오른쪽으로 이동합니다.

이를 위해 left의 위치는 middle의 위치보다 1이 큰 수인 7로 이동하며, right는 7로 그대로 유지합니다.

중앙값인 middle은 7이 됩니다.

 

middle이 가리키는 수가 11로 찾고자 하는 수가 되며, middle의 위치를 반환합니다.

1.3. 이진탐색 예제 소스

아래는 C++로 구현된 이진탐색(Binary Search) 소스입니다.

#include <iostream>
#include <cstdio>

using namespace std;

int main(int argc, char* argvp[])
{
    int n;
    scanf("%d", &n); //찾고 싶은 수 입력
    //정렬된 수
    int arr[] = { 0, 1, 3, 4, 6, 9, 10, 11, 13, 15, 19 };
    int left = 1; //수의 가장 왼쪽에 위치한 번호로 초기화
    int right = 10; //수의 가장 오른쪽에 위치한 번호로 초기화
    int middle;

    while (left <= right)
    {
        middle = (left + right) / 2;
        //middle에 위치한 값이 찾는 값이면 루프를 탈출
        if (arr[middle] == n)
            break;
        //middle에 위치한 값이 찾는 값보다 작으면 left를 middle+!로 이동 -> 찾는 범위를 우측으로 이동
        else if (arr[middle] < n)
            left = middle + 1;
        //middle에 위치한 값이 찾는 값보다 크면 right를 middle-1로 이동 -> 찾는 범위를 좌측으로 이동
        else if (arr[middle] > n)
            right = middle - 1;
    }
    //찾는 값의 위치를 출력한다.
    printf("%d\n", middle);

    return 0;
}

2. 파라메트릭 서치(Parametric Search)

2.1. 파라메트릭 서치란?

파라메트릭 서치는 이진탐색을 응용한 방식으로 기본적인 탐색 과정 또한 동일합니다.

배열의 특정한 값을 찾는 이진탐색은 중앙값(middle)이 가리키는 값이 내가 찾는 값인지 중요합니다.

반면, 파라메트릭 서치는 내가 원하는 조건을 만족하는 가장 알맞는 값을 찾는 것입니다.

따라서 이진탐색처럼 정해진 소스가 있는것이 아니라 사용자의 목적에 맞춰 조건을 정해야 합니다.

2.2. 파라메트릭 서치 탐색 과정

아래는 정렬된 10개의 수 1, 3, 4, 6, 9, 10, 11, 13, 15, 19에서 14보다 작은 수의 갯수를 구해보겠습니다.

이를 위해 조건으로 middle의 좌측과 우측의 값을 동시에 확인하는 방식으로 탐색을 할 예정입니다.

 

우선 처음엔 수의 가장 왼쪽 순번인 1을 left에 가장 오른쪽 순번인 10을 right로 저장하고 이에대한 중앙값인 5를 middle로 정합니다.

middle이 가리키는 값이 9로 찾고자 하는 14보다 작은 값입니다.

또한 middle 바로 오른쪽의 값도 10으로 찾고자 하는 값인 14보다 작습니다.

따라서 left의 값을 middle에다 1을 더한 값으로 변경합니다. right의 값은 그대로 유지합니다.

middle의 값은 새로 갱신하여 left와 right의 중간값인 8로 변경합니다.

middle이 가리키는 값은 13으로 14보다 작지만 middle의 바로 오른쪽에 있는값은 15로 14보다 큽니다.

따라서 middle의 위치인 8일 결과값입니다.

2.3. 파라메트릭 서치 예제 소스

아래는 C++로 구현된 파라메트릭 서치(Parametric Search) 소스입니다.

#include <iostream>
#include <cstdio>

using namespace std;

int main(int argc, char* argvp[])
{
    int n;
    scanf("%d", &n); //찾고 싶은 수 입력
                     //정렬된 수
    int arr[] = { 0, 1, 3, 4, 6, 9, 10, 11, 13, 15, 19 };
    int left = 1; //수의 가장 왼쪽에 위치한 번호로 초기화
    int right = 10; //수의 가장 오른쪽에 위치한 번호로 초기화
    int middle;
    int ans = 0;
    //middle에 위치한 값과 좌우 값을 비교하면서 조건을 만족하는지 확인
    while (left <= right)
    {
        middle = (left + right) / 2;
        //middle에 있는값이 찾는값과 같으면 그 앞에 있는값은 모두 찾는값보다 작다.
        if (arr[middle] == n)
        {
            ans = middle - 1;
            break;
        }
        //middle에 위치한 값이 찾는값보다 작고
        else if (arr[middle] < n)
        {
            //middle의 오른쪽에 있는값이 찾는값보다 크면 middle 갯수만큼 작은 수가 존재한다.
            if (middle < 10 && arr[middle + 1] > n)
            {
                ans = middle;
                break;
            }
            //주어진 수가 모두 작으면 수의 개수를 출력
            else if (middle == 10)
            {
                ans = 10;
                break;
            }
            //오늘쪽으로 슬라이드 하여 탐색
            else
                left = middle + 1;
        }
        //middle에 위치한 값이 찾는값보다 크고
        else if (arr[middle] > n)
        {
            //middle의 왼쪽에 있는값이 찾는값보다 작으면 middle-1개만큼 작은수가 존재
            if (middle > 1 && arr[middle - 1] < n)
            {
                ans = middle - 1;
                break;
            }
            //첫번째 수 조차 n보다 크면 0을 출력
            else if (middle == 1)
            {
                ans = 0;
                break;
            }
            //왼쪽으로 슬라이드 하여 탐색
            else
                right = middle - 1;
        }
    }
    //찾는 값의 위치를 출력한다.
    printf("%d\n", ans);

    return 0;
}