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

어떤 값을 비교했는지 보기

어떤 값을 비교했는지 보기

이번에 배울 것

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

실행해 보기

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가 값을 찾을 때 몇 번 비교했는지 count를 추가해 출력하세요.

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);
}