작은 걸음 III — 프로그램으로 생각하기

반씩 줄여서 찾기

반씩 줄여서 찾기

한 주제 안에서 차근차근 배워 봅니다. 예제를 하나씩 실행하고, 중간에 쉬었다가 이어서 해도 좋습니다. 마지막의 추가 연습은 원하는 만큼 해 보세요.

찾을 범위를 반으로 줄이기

이번에 배울 것

이진 검색은 가운데 값과 비교하여 가능한 범위를 반씩 줄이는 방법입니다. 배열이 먼저 작은 순서로 정렬되어 있어야 합니다.

실행해 보기

예제 · example1.cpp
int binary_search(Array<int> numbers, int value)
{
    int left = 0;
    int right = numbers.length() - 1;

    while (left <= right)
    {
        int middle = (left + right) / 2;

        if (numbers[middle] == value)
            return middle;

        if (value < numbers[middle])
            right = middle - 1;
        else
            left = middle + 1;
    }

    return -1;
}

void small_main()
{
    Array<int> numbers = {1, 3, 5, 7, 9, 11, 13};
    print(binary_search(numbers, 11));
}

left와 right는 남은 범위의 양 끝입니다. 가운데보다 찾는 값이 작으면 오른쪽 절반을, 크면 왼쪽 절반을 제외합니다.

11의 위치는 5입니다. 못 찾으면 -1을 돌려줍니다. 가운데 위치도 검사했으므로 다음 범위에서는 middle을 빼고 시작합니다.

어떤 값을 비교했는지 보기

이번에 배울 것

중간에 값을 출력하면 프로그램이 답을 찾는 과정을 추적할 수 있습니다.

실행해 보기

예제 · binary_search_2_example2.cpp
void small_main()
{
    Array<int> numbers = {2, 5, 8, 12, 16, 23, 38, 56};
    int value = 23;

    int left = 0;
    int right = numbers.length() - 1;
    int comparisons = 0;

    while (left <= right)
    {
        int middle = (left + right) / 2;
        comparisons = comparisons + 1;
        print("Checking ", numbers[middle]);

        if (numbers[middle] == value)
            break;

        if (value < numbers[middle])
            right = middle - 1;
        else
            left = middle + 1;
    }

    print("Comparisons: ", comparisons);
}

예제는 23을 찾으며 Checking 12, Checking 23을 출력합니다. 비교 횟수는 2입니다.

이번 예제는 비교 과정을 관찰하는 용도입니다. value를 없는 값으로 바꾸면 범위가 비어 끝나지만, 별도의 성공 안내는 출력하지 않습니다.

Exercise — Binary Search 완성

정렬된 {4, 8, 15, 16, 23, 42}에서 23을 찾아 index를 출력하는 Binary Search를 작성하세요.

연습 문제 코드 · exercise1_starter.cpp
void small_main()
{
    Array<int> numbers = {4, 8, 15, 16, 23, 42};
    int value = 23;
    int index = -1;

    // Binary Search here.

    print(index);
}

Hint

left, right, middle 세 변수를 사용하고 매번 범위를 절반으로 줄이세요.

풀이 보기
void small_main()
{
    Array<int> numbers = {4, 8, 15, 16, 23, 42};
    int value = 23;
    int index = -1;
    int left = 0;
    int right = numbers.length() - 1;

    while (left <= right)
    {
        int middle = (left + right) / 2;

        if (numbers[middle] == value)
        {
            index = middle;
            break;
        }

        if (value < numbers[middle])
            right = middle - 1;
        else
            left = middle + 1;
    }

    print(index);
}
더 해 보기 (선택)

Exercise — 비교 횟수 세기

Binary Search가 값을 찾을 때 몇 번 비교했는지 count를 추가해 출력하세요.

연습 문제 코드 · binary_search_2_exercise2_starter.cpp
void small_main()
{
    Array<int> numbers = {1, 3, 5, 7, 9, 11, 13, 15, 17};
    int value = 17;
    int comparisons = 0;

    // Binary Search and count comparisons.

    print("Comparisons: ", comparisons);
}

Hint

while을 한 번 돌 때마다 comparisons를 1 증가시키세요.

풀이 보기
void small_main()
{
    Array<int> numbers = {1, 3, 5, 7, 9, 11, 13, 15, 17};
    int value = 17;
    int comparisons = 0;
    int left = 0;
    int right = numbers.length() - 1;

    while (left <= right)
    {
        int middle = (left + right) / 2;
        comparisons = comparisons + 1;

        if (numbers[middle] == value)
            break;

        if (value < numbers[middle])
            right = middle - 1;
        else
            left = middle + 1;
    }

    print("Comparisons: ", comparisons);
}
← 이전 레슨다음 레슨 →