Small Steps III — Thinking with Programs

Find a Value

Find a Value

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.

Searching 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

Example · example1.cpp
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.

Handling the not-found case

What you will learn

A search can succeed or fail. The program should distinguish and report both cases.

Try it

Example · linear_search_2_example2.cpp
void small_main()
{
    Array<int> numbers = {7, 2, 9, 4, 5};
    int value = input_int("Find: ");
    int index = -1;

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

    if (index == -1)
        print("Not found");
    else
        print("Found at ", index);
}

Entering 9 in the console produces Found at 2; entering 8 produces Not found.

Here, break ends only the search loop, and the following if prints the result. Distinguish this from return, which ends the whole function.

Exercise

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

Exercise starter · exercise1_starter.cpp
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.

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

Exercise

Use a linear search to find and print the first position of the character 'a' in a String. Use -1 if absent.

Exercise starter · linear_search_2_exercise2_starter.cpp
void small_main()
{
    String text = "Small C++";
    int index = -1;

    // find the first 'a'.

    print(index);
}

Hint

String also supports length and [], so this is almost the same as searching an Array.

show solution
void small_main()
{
    String text = "Small C++";
    int index = -1;

    for (int i = 0; i < text.length(); i = i + 1)
        if (text[i] == 'a')
        {
            index = i;
            break;
        }

    print(index);
}
← Previous lessonNext lesson →