C++: best, worst, and average case of linear search
The running time of an algorithm often depends on which input of a given size it receives. Linear search stops as soon as it finds the target, so its best case is one comparison, when the target is first. Its worst case is n comparisons, when the target is last or absent.
C++
#include <iostream>
#include <vector>
int comparisons = 0;
int linear_search(const std::vector<int>& values, int target) {
for (std::size_t i = 0; i < values.size(); ++i) {
++comparisons;
if (values[i] == target) {
return static_cast<int>(i);
}
}
return -1;
}
int main() {
std::vector<int> values = {7, 3, 9, 1, 5, 8, 2, 6};
int n = static_cast<int>(values.size());
comparisons = 0;
linear_search(values, 7);
std::cout << "best case: " << comparisons << "\n";
comparisons = 0;
linear_search(values, 6);
std::cout << "worst case, last item: " << comparisons << "\n";
comparisons = 0;
linear_search(values, 100);
std::cout << "absent: " << comparisons << "\n";
int total = 0;
for (int v : values) {
comparisons = 0;
linear_search(values, v);
total += comparisons;
}
std::cout << "average over present items: " << static_cast<double>(total) / n << "\n";
}