Small Steps III — Thinking with Programs

Search by Halving

Search by Halving

Explore one topic in small steps. Try the examples one at a time and take a break whenever you need. Choose how many extra exercises you want to try.

Halving the search range

What you will learn

Binary search compares with the middle value and repeatedly halves the possible range. The array must first be sorted from smallest to largest.

Try it

Example · 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 and right mark the remaining range's ends. If the target is smaller than the middle value, discard the right half; if larger, discard the left half.

11 is at position 5. Return -1 if not found. Because middle was already checked, exclude it from the next range.

Seeing which values were compared

What you will learn

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

Try it

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

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

Write Binary Search to find 23 in the sorted array {4, 8, 15, 16, 23, 42} and print its index.

Exercise starter · 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

Use left, right, and middle, reducing the range by half each time.

show solution
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);
}
Try More (Optional)

Exercise

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

Exercise starter · 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

Increase comparisons by 1 each time the while loop runs.

show solution
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);
}
← Previous lessonNext lesson →