Small Steps III — Thinking with Programs

Halving the search range

Halve 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

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.

Exercise

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

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.

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