C++ Searching Algorithms
Searching algorithms are tools that find values in a collection and answer questions about them. Each tool answers a different kind of question.
Finding a value and a missing value
std::find locates 37 and its position prints as an index. A search for 99 reaches the end position, so the other branch prints.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> values = {12, 25, 37, 48, 59};
auto found = std::find(values.begin(), values.end(), 37);
std::cout << "Position of 37: " << found - values.begin() << "\n";
auto missing = std::find(values.begin(), values.end(), 99);
if (missing == values.end()) {
std::cout << "99 not found\n";
}
return 0;
}Counting matches and passes
std::count counts the exact value 72. std::count_if counts values that pass the named predicate function.
#include <iostream>
#include <vector>
#include <algorithm>
bool isPassing(int score) {
return score >= 50;
}
int main() {
std::vector<int> scores = {48, 72, 85, 49, 90, 72};
int exact = std::count(scores.begin(), scores.end(), 72);
int passing = std::count_if(scores.begin(), scores.end(), isPassing);
std::cout << "Count of 72: " << exact << "\n";
std::cout << "Passing: " << passing << "\n";
return 0;
}Binary search on sorted values
The vector is already sorted, so std::binary_search can answer each question. One value is present and one is absent.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> values = {10, 20, 30, 40, 50};
std::cout << std::boolalpha;
std::cout << "30 found: " << std::binary_search(values.begin(), values.end(), 30) << "\n";
std::cout << "35 found: " << std::binary_search(values.begin(), values.end(), 35) << "\n";
return 0;
}Where a value would sit
std::lower_bound finds the first position not less than 35. That position holds 40, and its index prints.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> values = {10, 20, 30, 40, 50};
auto spot = std::lower_bound(values.begin(), values.end(), 35);
std::cout << "Position: " << spot - values.begin() << "\n";
std::cout << "Value there: " << *spot << "\n";
return 0;
}Example
#include <iostream>
#include <vector>
#include <algorithm>
bool isPassing(int score) {
return score >= 60;
}
int main() {
std::vector<int> results = {65, 80, 92, 80, 71};
auto found = std::find(results.begin(), results.end(), 92);
std::cout << "Position of 92: " << found - results.begin() << "\n";
std::cout << "Count of 80: " << std::count(results.begin(), results.end(), 80) << "\n";
std::cout << "Passing: " << std::count_if(results.begin(), results.end(), isPassing) << "\n";
return 0;
}Key points
- std::find returns the position of the first matching value.
- std::find returns the end position when no value matches.
- Subtracting begin from a position gives the index of that position.
- std::count counts how many values match a given value.
- std::count_if counts values that pass a named predicate function.
- std::binary_search needs sorted values and answers true or false.
- std::lower_bound finds the first position where a value could sit in sorted order.
In this example, three searching tools answer three questions about the same results. std::find gives the position of 92, and std::count gives the number of 80 values. std::count_if uses the named predicate to count all five passing results.
Note
The maps lesson used lower_bound on a map, and this lesson uses the same idea on a vector.
Try it Yourself
Edit the code, then press Run.
Running is simulated
Exercise
What does std::find return when no value matches?