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