C: best, worst, and average case of linear search
The running time of an algorithm often depends on the particular input, not just its size. Linear search stops as soon as the target is found. Its best case is one comparison, when the target is the first item. Its worst case is n comparisons, when the target is last or missing.
C
#include <stdio.h>
static int comparisons = 0;
static int linear_search(const int *values, int n, int target) {
for (int i = 0; i < n; i++) {
comparisons++;
if (values[i] == target) {
return i;
}
}
return -1;
}
int main(void) {
int values[] = {7, 3, 9, 1, 5, 8, 2, 6};
int n = (int)(sizeof values / sizeof values[0]);
comparisons = 0;
linear_search(values, n, 7);
printf("best case: %d\n", comparisons);
comparisons = 0;
linear_search(values, n, 6);
printf("worst case, last item: %d\n", comparisons);
comparisons = 0;
linear_search(values, n, 100);
printf("absent: %d\n", comparisons);
int total = 0;
for (int i = 0; i < n; i++) {
comparisons = 0;
linear_search(values, n, values[i]);
total += comparisons;
}
printf("average over present items: %.1f\n", (double)total / n);
return 0;
}