Small Steps III — Thinking with Programs

Seeing which values were compared

See which values were compared.

What you will learn

Printing intermediate values lets you trace how a program finds its answer.

Try it

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

The example searches for 23 and prints Checking 12 and Checking 23. There are 2 comparisons.

This example is for observing comparisons. Changing value to an absent value ends the loop when the range becomes empty, but it does not print a separate success message.

Exercise

Add a counter to Binary Search and print how many comparisons it made to find the value.

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

Increase comparisons by 1 each time the while loop runs.

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