Linear Search
GOALLook for a value in an array and report where it is.
The simplest search there is: start at the front and check each cell. Stop the moment you find it. If it is not there, returning -1 is the convention for "not found".
ON THIS PAGE
//THE EXAMPLE
#include <iostream>
#include <vector>
using namespace std;
int find(const vector<int>& v, int target) {
for (int i = 0; i < (int)v.size(); i++) {
if (v[i] == target) {
return i;
}
}
return -1;
}
int main() {
vector<int> v = {4, 8, 15, 16, 23, 42};
cout << find(v, 15) << endl;
cout << find(v, 99) << endl;
return 0;
}2 -1
//LINE BY LINE
Watch it run
i = 0. v[0] = 4, which is not 15. Keep going.
The first one, or all of them?
A problem that says "find" can be asking three different things. Get it wrong and your code is almost right, which is still wrong.
| The question | What to do |
|---|---|
| Байна уу? / Is it there? | Олонгуут true буцаа / return true on the first hit |
| Хаана байна? / Where is it? | Олонгуут индексийг буцаа / return the index on the first hit |
| Хэдэн ширхэг вэ? / How many? | БҮГДИЙГ шалга, тоол / check them ALL and count |
Stopping early in a counting problem makes the answer always 1. Searching and counting are different loops.
Saying "not found"
If a function returns an index it still has to be able to say "not found". An index is never negative, so -1 makes a safe marker.
int pos = find(v, 42);
if (pos == -1) {
cout << "not in the list" << endl;
} else {
cout << "at index " << pos << endl;
}Never use 0 for "not found" — 0 is a real index. The bug only shows up on the first element, which makes it hard to spot.