Small Steps III — Thinking with Programs

Searching for a value

Search for a value.

What you will learn

Searching determines whether a value exists and, if so, where it is. Comparing values one by one from the beginning is called linear search.

Try it

int find(Array<int> numbers, int value)
{
    for (int i = 0; i < numbers.length(); i = i + 1)
        if (numbers[i] == value)
            return i;

    return -1;
}

void small_main()
{
    Array<int> numbers = {7, 2, 9, 4, 5};
    print("Index: ", find(numbers, 9));
}

9 is at position 2, so the output is Index: 2. When found, return gives back the position and ends the whole function.

If the value is not found by the end, return -1. Valid positions are at least 0, so -1 was chosen to mean not found.

Exercise

When a value appears several times, find its last index. Print -1 if it does not occur.

void small_main()
{
    Array<int> numbers = {3, 7, 2, 7, 5, 7};
    int value = 7;
    int index = -1;

    // find the last position.

    print(index);
}

Hint

Instead of returning at the first match, update the index and keep looking to the end.

void small_main()
{
    Array<int> numbers = {3, 7, 2, 7, 5, 7};
    int value = 7;
    int index = -1;

    for (int i = 0; i < numbers.length(); i = i + 1)
        if (numbers[i] == value)
            index = i;

    print(index);
}