Section 26.1 Searching
Searching is the algorithmic process of finding a particular item in a collection of items. Depending on the needs of the algorithm, and the kind of collection being searched, a search might produce
true or false as to whether the item is present. Or it might return a location where the item is found (and a special value if it is not found). Or, it might return the item itself. Of these options, returning a location is the most generally useful. Given a location, the caller can decide “is the item” present. They can also use the location to retried or modify the item.
A linear search is a simple searching algorithm that checks each element in a list sequentially until the desired element is found or the end of the list is reached. Try out the interactive below. Try searching for a value that is in the list, and then one that is not in the list.
The algorithm needs to keep track of the value it is looking (sometimes referred to as the key) for and the index it is currently checking. As soon as it finds the key, it can stop searching. If the key is not found, the search ends after checking the last element.
Implemented to search a vector in C++, it looks like this:
Note 26.1.1.
This version of the function returns -1 to indicate that the element was not found in the vector. This is a common convention in most programming languages.
However, in C++ library code for classes like string, locations are represented using unsigned types and thus -1 cannot be used to indicate "not found". Instead, a special constant like
string::npos is used. If that value is cast as an int, it becomes -1.
Checkpoint 26.1.1.
Which statements are true about linear search?
- In the worst case, it checks every element in the list.
- Returning true or false is the most useful result to produce.
- It requires that the data be in order.
- It always has to check every element in the list.
- -1 is a common convention to indicate "not found".
You have attempted of activities on this page.
