On a sorted array of 128 ints, a plain linear search found a random key in 43.6 nanoseconds, and binary search took 46.7. At 4,096 ints the order reversed: binary search took 81 ns and linear search 841. Linear search is the slow algorithm in every textbook, yet for small arrays it was the faster one on the machine used for this article, and it is the only option when the data is not sorted.
This guide explains how linear search works and what it costs, then builds it in C and C++: the plain loop, a generic search for any element type, the sentinel version, self-organizing move-to-front and transpose, a program that searches numbers read safely from a file, and the C++ standard library’s std::find and std::find_if. It measures the comparisons each version makes and where binary search overtakes it, and shows three mistakes that break linear searches. Every program was compiled and run for this article on Ubuntu 24.04 (x86-64), and again under WSL and with MSVC on Windows: C with GCC 13.3 and Clang 18.1.3 under -std=c11 and -std=c17, C++ with g++ 13.3 and clang++ 18.1.3 under -std=c++17 and -std=c++20, all with -Wall -Wextra -pedantic -Werror and no warnings. The search functions’ tests run clean under AddressSanitizer, UndefinedBehaviorSanitizer and Valgrind, and every output block is captured verbatim. The code is in two GitHub repositories whose workflows repeat these checks on each commit.
What Is Linear Search?
Linear search, also called sequential search, checks the elements of a list one at a time, from the first, until it finds one equal to the key or reaches the end. It needs no sorting or other preparation and works on any sequence, but it takes O(n) time: on average about half the elements for a key that is present, and all of them for a key that is not.
Its cost is easy to state exactly. For an array of n elements:
| Case | Comparisons | When it happens |
|---|---|---|
| Best | 1 | The key is the first element |
| Average, key present | (n + 1) / 2 | Every position equally likely |
| Worst, key present | n | The key is the last element |
| Key not present | n | Every element is checked |
The average is a prediction worth testing. Searching 1,000,000 times for random keys in a shuffled array of 100 distinct numbers took 50.49 comparisons per search, against the predicted (100 + 1) / 2 = 50.50; a missing key always took 100 (the full program and output are in the move-to-front section).
Linear search is the right tool more often than its O(n) suggests: for unsorted data searched only a few times, for linked lists and other sequences without random access, for small arrays, and whenever the condition is not simple equality, such as “the first product that costs more than 3.00”.
How Linear Search Works, Step by Step
Searching the array 42 7 19 73 7 0 -5 88 for 73:
- Index 0: 42 is not 73; move on.
- Index 1: 7 is not 73; move on.
- Index 2: 19 is not 73; move on.
- Index 3: 73 equals the key. Return 3, after 4 comparisons.
Searching for 50 checks all eight elements, finds no match and returns −1, the usual “not found” value for an index. Searching for 7 returns 1, the first of its two positions: a linear search scanning from the front always reports the first match.
Linear Search in C
The library’s basic function searches an array of int, the simplest of the arrays in C and C++, and returns the index of the first match, or −1:
ptrdiff_t linear_search(const int *a, size_t n, int key)
{
for (size_t i = 0; i < n; i++)
if (a[i] == key)
return (ptrdiff_t)i;
return -1;
}
The parameters follow two habits of reliable C. The array is const int *, because a search should not modify what it searches, and the length is a size_t, the type C uses for sizes. The result is a ptrdiff_t, a signed type wide enough to hold any array index and −1, which an int cannot guarantee for very large arrays. The loop condition is i < n: the last valid index is n - 1.
The demo runs every function in the library on small examples:
/* linear_search_demo.c - the examples from the article. */
#include <stdio.h>
#include <string.h>
#include "linear_search.h"
typedef struct {
const char *name;
double price;
} Product;
static bool has_name(const void *element, const void *ctx)
{
return strcmp(((const Product *)element)->name, (const char *)ctx) == 0;
}
static void print_array(const char *label, const int *a, size_t n)
{
printf("%-22s", label);
for (size_t i = 0; i < n; i++)
printf(" %d", a[i]);
printf("\n");
}
int main(void)
{
int a[] = {42, 7, 19, 73, 7, 0, -5, 88};
const size_t n = sizeof a / sizeof a[0];
const int keys[] = {73, 7, 0, 88, 50};
print_array("array:", a, n);
for (size_t k = 0; k < sizeof keys / sizeof keys[0]; k++) {
ptrdiff_t at = linear_search(a, n, keys[k]);
if (at >= 0)
printf("%3d found at index %td after %td comparisons\n", keys[k], at, at + 1);
else
printf("%3d not found after %zu comparisons\n", keys[k], n);
}
ptrdiff_t found = sentinel_search(a, n, 88);
ptrdiff_t missing = sentinel_search(a, n, 50);
printf("sentinel search for 88: index %td, for 50: %td\n", found, missing);
print_array("array afterwards:", a, n);
const Product shelf[] = {{"pen", 1.25}, {"notebook", 3.5}, {"stapler", 7.0}};
const Product *p = search_first(shelf, 3, sizeof shelf[0], has_name, "notebook");
printf("search_first for \"notebook\": %s at index %td, price %.2f\n",
p ? p->name : "none", p ? p - shelf : -1, p ? p->price : 0.0);
int list[] = {1, 2, 3, 4, 5, 6};
const int lookups[] = {5, 5, 6, 5};
for (size_t k = 0; k < sizeof lookups / sizeof lookups[0]; k++) {
char label[32];
ptrdiff_t at = search_move_to_front(list, 6, lookups[k]);
snprintf(label, sizeof label, "find %d (was at %td):", lookups[k], at);
print_array(label, list, 6);
}
const int sorted[] = {-5, 0, 7, 7, 19, 42, 73, 88};
printf("binary search in sorted copy for 7: index %td, for 50: %td\n",
binary_search(sorted, 8, 7), binary_search(sorted, 8, 50));
return 0;
}
Output:
array: 42 7 19 73 7 0 -5 88
73 found at index 3 after 4 comparisons
7 found at index 1 after 2 comparisons
0 found at index 5 after 6 comparisons
88 found at index 7 after 8 comparisons
50 not found after 8 comparisons
sentinel search for 88: index 7, for 50: -1
array afterwards: 42 7 19 73 7 0 -5 88
search_first for "notebook": notebook at index 1, price 3.50
find 5 (was at 4): 5 1 2 3 4 6
find 5 (was at 0): 5 1 2 3 4 6
find 6 (was at 5): 6 5 1 2 3 4
find 5 (was at 1): 5 6 1 2 3 4
binary search in sorted copy for 7: index 2, for 50: -1
The comparison counts are the returned index plus one for a hit and n for a miss, which is how the measurements in this article count them without instrumenting the loop.
Searching Any Type: a Generic Linear Search
The int version cannot search an array of structs or strings. search_first takes the same approach as the C library’s lfind() and qsort(): the array is passed as const void * with the size of one element, and the caller supplies a function that decides whether an element matches.
void *search_first(const void *base, size_t n, size_t size,
bool (*match)(const void *element, const void *ctx), const void *ctx)
{
const unsigned char *p = base;
for (size_t i = 0; i < n; i++, p += size)
if (match(p, ctx))
return (void *)p;
return NULL;
}
The pointer steps by size bytes, so it lands on the start of each element whatever its type. The ctx argument carries the key, or anything else the match function needs; in the demo it is the name "notebook", compared with strcmp. Returning a pointer instead of an index gives the caller the element itself, and NULL means “not found”.
POSIX systems also have lfind() in <search.h>, which compares with a function returning 0 for a match. A test on Linux compares linear_search with it on 10,000 random arrays:
random arrays where linear_search and lfind agree: 10000 of 10000
lfind() is a POSIX function, not standard C, so the library does not depend on it and this test runs only on Linux.
The Sentinel Trick
The plain loop makes two tests per element: i < n and a[i] == key. If the key is certain to be found, the first test is unnecessary. The sentinel version makes it certain by temporarily writing the key into the last element, so the loop needs only the equality test:
ptrdiff_t sentinel_search(int *a, size_t n, int key)
{
if (n == 0)
return -1;
int last = a[n - 1];
a[n - 1] = key; /* the loop below is now sure to stop */
size_t i = 0;
while (a[i] != key)
i++;
a[n - 1] = last;
if (i < n - 1 || last == key)
return (ptrdiff_t)i;
return -1;
}
When the loop stops at the last position, the function checks whether that was the sentinel or a real match by looking at the saved value. This is the “quick sequential search” of Knuth’s The Art of Computer Programming, volume 3, section 6.1 (Algorithm Q), which places the key one past the end of the table; replacing the last element instead, as here, needs no spare slot.
The price is that the search writes to the array. It cannot take a const array, it must not run while another thread reads the same array, and it must restore the last element on every path. The demo’s “array afterwards” line and a test on 20,000 random arrays check that it does. What the trick saves in time is measured below: on this machine, at most about 12 percent, and not in every run.
Self-Organizing Lists: Move-to-Front and Transpose
When some keys are searched for far more often than others, the order of the array matters more than the loop. A self-organizing list rearranges itself on every hit so that popular keys drift to the front:
- Move-to-front: the element found moves to index 0, and those before it shift back one place.
- Transpose: the element found swaps places with the one before it, moving forward one step per hit.
ptrdiff_t search_move_to_front(int *a, size_t n, int key)
{
ptrdiff_t at = linear_search(a, n, key);
if (at > 0) {
for (size_t i = (size_t)at; i > 0; i--) /* shift the others back */
a[i] = a[i - 1];
a[0] = key;
}
return at;
}
ptrdiff_t search_transpose(int *a, size_t n, int key)
{
ptrdiff_t at = linear_search(a, n, key);
if (at > 0) {
a[at] = a[at - 1];
a[at - 1] = key;
}
return at;
}
Both were analysed by Rivest (1976). The comparison program below measures them on 100 distinct keys requested with Zipf frequencies, where the k-th most popular key is asked for about 1/k as often as the first, a common model for real lookup traffic. It also computes the best any fixed order could do: the keys sorted by popularity.
/* comparisons.c - average number of comparisons per search, counted
* exactly from the index each search returns, for 100 distinct keys in a
* shuffled array:
* - every key equally likely, and keys that are not in the array;
* - keys asked for with Zipf frequencies (key k about 1/k as often as
* key 1), searched with the plain loop, move-to-front and transpose,
* and the best any fixed order can do. */
#include <stdint.h>
#include <stdio.h>
#include "linear_search.h"
#define N 100
#define SEARCHES 1000000
static uint64_t state = 42;
static uint64_t next_random(void) /* splitmix64 */
{
uint64_t z = (state += 0x9e3779b97f4a7c15u);
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9u;
z = (z ^ (z >> 27)) * 0x94d049bb133111ebu;
return z ^ (z >> 31);
}
static void shuffled(int *a)
{
for (int k = 0; k < N; k++)
a[k] = k + 1;
for (int k = N - 1; k > 0; k--) { /* Fisher-Yates */
int j = (int)(next_random() % (uint64_t)(k + 1)), t = a[k];
a[k] = a[j];
a[j] = t;
}
}
/* Integer Zipf weights, so every platform draws the same keys. */
static uint64_t weight[N + 1], total;
static int zipf_key(void)
{
uint64_t r = next_random() % total;
int k = 1;
while (r >= weight[k])
r -= weight[k++];
return k;
}
int main(void)
{
int a[N];
uint64_t sum = 0;
shuffled(a);
for (int s = 0; s < SEARCHES; s++)
sum += (uint64_t)linear_search(a, N, (int)(next_random() % N) + 1) + 1;
printf("uniform keys, found: %6.2f comparisons (predicted (n + 1) / 2 = %.2f)\n",
(double)sum / SEARCHES, (N + 1) / 2.0);
printf("keys not in the array: %6d comparisons (always n)\n", N);
for (int k = 1; k <= N; k++)
total += weight[k] = 1000000 / (uint64_t)k;
double best = 0;
for (int k = 1; k <= N; k++) /* most frequent first */
best += (double)k * (double)weight[k] / (double)total;
const char *names[] = {"plain loop", "move-to-front", "transpose"};
for (int method = 0; method < 3; method++) {
shuffled(a);
sum = 0;
for (int s = 0; s < SEARCHES; s++) {
int key = zipf_key();
ptrdiff_t at = method == 0 ? linear_search(a, N, key)
: method == 1 ? search_move_to_front(a, N, key)
: search_transpose(a, N, key);
sum += (uint64_t)at + 1;
}
printf("Zipf keys, %-16s %6.2f comparisons\n", names[method], (double)sum / SEARCHES);
}
printf("Zipf keys, %-16s %6.2f comparisons\n", "best fixed order", best);
return 0;
}
Output:
uniform keys, found: 50.49 comparisons (predicted (n + 1) / 2 = 50.50)
keys not in the array: 100 comparisons (always n)
Zipf keys, plain loop 39.66 comparisons
Zipf keys, move-to-front 26.28 comparisons
Zipf keys, transpose 19.71 comparisons
Zipf keys, best fixed order 19.28 comparisons
Move-to-front cut the average from 39.66 comparisons to 26.28 and transpose to 19.71, close to the 19.28 of the best fixed order, without knowing the frequencies in advance. The plain loop’s 39.66 depends on where the shuffle happened to put the popular keys; any arrangement averages 50.5 over many shuffles. The two strategies trade off differently in practice: move-to-front reacts at once when popularity changes, while transpose settles closer to the best order for steady traffic. Both cost writes on every successful search, so neither suits data that is shared or read-only.
A Practical Program: Searching Numbers From a File
Programs that read numbers interactively are where most linear-search examples go wrong, so search_numbers reads them carefully: whole lines with fgets, each token checked with strtol for garbage, trailing characters and out-of-range values, and errors reported with the line number.
search_numbers FILE KEY... or search_numbers - KEY... < FILE
Given a file with the demo’s eight numbers spread over three lines:
$ search_numbers numbers.txt 73 0 50
73: number 4 of 8
0: number 6 of 8
50: not found among 8 numbers
The exit status is 0 if every key was found, 1 if any was missing (as here, for 50), and 2 for an error. A file containing the word five is rejected instead of being read as some number:
$ search_numbers bad.txt 4
tests/data/bad.txt:2: not a whole number: five
exit status 2
Positions are printed counting from 1 (“number 4 of 8”), which is what a person reading the file expects; the function itself returns the 0-based index 3. Mixing the two is a common source of off-by-one reports.
Linear Search in C++
C++ programs rarely need to write the loop. std::find returns an iterator to the first element equal to a value, or the end iterator if there is none, and std::find_if takes a condition instead. Both work on every standard container. The program below adds a generic find_index that works on any container with begin() and end(), including std::list, and implements move-to-front with std::rotate:
// linear_search.cpp - linear search in C++17: a generic function, the
// standard library's std::find and std::find_if, move-to-front with
// std::rotate, and std::lower_bound for sorted data.
// Build: g++ -std=c++17 -Wall -Wextra -pedantic linear_search.cpp -o linear_search
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <list>
#include <optional>
#include <string>
#include <vector>
// Position of the first element equal to value in any container that can be
// walked from begin() to end(), or std::nullopt.
template <class Container, class T>
std::optional<std::size_t> find_index(const Container& c, const T& value)
{
std::size_t i = 0;
for (const auto& element : c) {
if (element == value)
return i;
++i;
}
return std::nullopt;
}
// Moves the first element equal to value to the front and returns where it
// was, or std::nullopt. std::rotate shifts the elements before it back by one.
template <class T>
std::optional<std::size_t> move_to_front(std::vector<T>& v, const T& value)
{
const auto it = std::find(v.begin(), v.end(), value);
if (it == v.end())
return std::nullopt;
const auto at = static_cast<std::size_t>(it - v.begin());
std::rotate(v.begin(), it, it + 1);
return at;
}
struct Product {
std::string name;
double price;
};
namespace {
void print(const char* label, const std::vector<int>& v)
{
std::cout << label;
for (const int x : v)
std::cout << ' ' << x;
std::cout << '\n';
}
void report(const char* what, std::optional<std::size_t> at)
{
std::cout << what << ": ";
if (at)
std::cout << "index " << *at << '\n';
else
std::cout << "not found\n";
}
} // namespace
int main()
{
const std::vector<int> numbers{42, 7, 19, 73, 7, 0, -5, 88};
report("find_index 73 in a vector", find_index(numbers, 73));
report("find_index 50 in a vector", find_index(numbers, 50));
const std::list<std::string> words{"red", "green", "blue"};
report("find_index \"blue\" in a list", find_index(words, std::string("blue")));
// std::find returns an iterator: end() means "not found".
const auto it = std::find(numbers.begin(), numbers.end(), 7);
std::cout << "std::find 7: index " << std::distance(numbers.begin(), it) << '\n';
// std::find_if takes a condition instead of a value.
const std::vector<Product> shelf{{"pen", 1.25}, {"notebook", 3.5}, {"stapler", 7.0}};
const auto p = std::find_if(shelf.begin(), shelf.end(),
[](const Product& x) { return x.price > 3.0; });
if (p != shelf.end())
std::cout << "first product over 3.00: " << p->name << '\n';
std::vector<int> list{1, 2, 3, 4, 5, 6};
for (const int key : {5, 5, 6, 5}) {
const auto was = move_to_front(list, key);
std::cout << "find " << key << " (was at " << (was ? static_cast<long>(*was) : -1L) << "):";
print("", list);
}
// For sorted data, std::lower_bound finds the first element >= value.
const std::vector<int> sorted{-5, 0, 7, 7, 19, 42, 73, 88};
const auto lb = std::lower_bound(sorted.begin(), sorted.end(), 7);
std::cout << "std::lower_bound 7 in the sorted copy: index " << (lb - sorted.begin()) << '\n';
return 0;
}
Output:
find_index 73 in a vector: index 3
find_index 50 in a vector: not found
find_index "blue" in a list: index 2
std::find 7: index 1
first product over 3.00: notebook
find 5 (was at 4): 5 1 2 3 4 6
find 5 (was at 0): 5 1 2 3 4 6
find 6 (was at 5): 6 5 1 2 3 4
find 5 (was at 1): 5 6 1 2 3 4
std::lower_bound 7 in the sorted copy: index 2
find_index returns std::optional<std::size_t>, which makes “not found” a separate state instead of a magic −1. std::rotate(v.begin(), it, it + 1) moves the element at it to the front and shifts the ones before it back, the same move-to-front as the C loop, and its sequence of results matches the C demo exactly. Strings compare by content with == in C++, so find_index(words, std::string("blue")) works, unlike == on C strings (see the mistakes below). In C++20, std::ranges::find(v, 7) takes the whole container instead of two iterators.
Linear Search vs Binary Search: When Is Linear Faster?
Binary search halves the remaining range at every step, so it needs about log₂ n comparisons instead of n / 2, but it only works on sorted data. The library’s version returns the first match, like the linear search, which matters when keys repeat:
ptrdiff_t binary_search(const int *a, size_t n, int key)
{
size_t lo = 0, hi = n; /* the first element >= key is at lo..hi */
while (lo < hi) {
size_t mid = lo + (hi - lo) / 2;
if (a[mid] < key)
lo = mid + 1;
else
hi = mid;
}
return lo < n && a[lo] == key ? (ptrdiff_t)lo : -1;
}
Writing the midpoint as lo + (hi - lo) / 2 keeps it correct for any array size; (lo + hi) / 2 could overflow only for arrays larger than half the address space, which is why the mutation tests below treat that change as harmless. Fewer comparisons do not automatically mean less time, so the two were timed.
How This Was Measured
| Setting | Value |
|---|---|
| Date tested | November 16, 2026 |
| Hardware | Cloud VM, 2 vCPUs, Intel Xeon @ 2.10 GHz |
| Operating system | Ubuntu 24.04.5 LTS, x86-64 |
| Compiler | GCC 13.3.0, CMake Release build (-O3 -DNDEBUG); the search functions are in a separate file, so they are not inlined into the loop |
| Input | Sorted arrays of distinct ints, 4 to 4,096 elements; 2,000,000 keys drawn at random from the array, so every search succeeds |
| What is timed | 2,000,000 calls to each function, divided by 2,000,000 |
| Statistic | Median of 5 runs |
| Check | The three functions must return the same indices, or the program exits |
All figures come from one machine, single-threaded, with no CPU pinning or frequency-scaling control and no percentiles. The crossover point depends on the processor, the compiler and the data; treat it as an order of magnitude, not a constant.
n linear sentinel binary
4 10.7 10.1 14.1
8 13.2 12.2 20.0
16 16.1 14.2 26.3
32 22.9 20.2 35.6
64 29.3 25.8 39.2
128 43.6 39.9 46.7
256 71.6 68.3 54.5
512 115.5 109.4 62.4
1024 217.7 205.7 68.2
4096 841.3 820.7 81.1
Linear search was faster up to 128 elements and binary search from 256 on. At 4 elements linear search took 10.7 ns and binary search 14.1; at 4,096 elements binary search took 81.1 ns and linear search 841.3, more than ten times as long. Linear search’s time grows in proportion to n, about 0.2 ns per element of the array at the large sizes, while binary search’s grows by 6 to 8 ns each time the array doubles.
Two things explain the small-array result, as far as these measurements can show. Linear search walks memory in order, which the processor’s prefetcher handles well, and its loop branch goes the same way until the match. Binary search’s branch goes left or right unpredictably for random keys, and a mispredicted branch costs more than several extra comparisons. That explanation is an inference from the shape of the results, not from a hardware profile.
The sentinel version was 2 to 12 percent faster than the plain loop in this run. In an earlier run of the same program it was faster from 8 to 512 elements but slower at 4, 1,024 and 4,096, so on this machine the saving is small and not reliable. A likely reason is that a modern processor executes the extra i < n test alongside the comparison, which leaves the trick less to save than it had on older machines.
Sorting has its own cost, so binary search pays off only when the same data is searched many times. The comparison of sorting algorithms in C and C++ measures what that first step costs.
Three Mistakes That Break a Linear Search
1. A loop that runs one step too far
i <= n instead of i < n reads one element past the end. Whether anything notices depends on what happens to be there:
/* off_by_one.c - a linear search whose loop runs one step too far,
* i <= n instead of i < n.
*
* off_by_one the array sits in a struct, so the int "after" it is
* the next field, and a missing key is found there
* off_by_one heap the same search on a copy in its own heap block */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct record {
int scores[5];
int id; /* the int right after the array */
};
static int search(const int *a, int n, int key)
{
for (int i = 0; i <= n; i++) /* should be i < n */
if (a[i] == key)
return i;
return -1;
}
int main(int argc, char **argv)
{
struct record r = {{12, 47, 33, 90, 61}, 99};
if (argc > 1 && strcmp(argv[1], "heap") == 0) {
int *copy = malloc(sizeof r.scores);
if (copy == NULL)
return 1;
memcpy(copy, r.scores, sizeof r.scores);
printf("search for 99 in a heap copy: %d\n", search(copy, 5, 99));
free(copy);
return 0;
}
printf("search for 33: %d\n", search(r.scores, 5, 33));
printf("search for 99: %d\n", search(r.scores, 5, 99)); /* 99 is not a score */
return 0;
}
Output (GCC and Clang, at -O0 and -O2):
search for 33: 2
search for 99: 5
99 is not one of the scores, but the search reports it at index 5, because the int after the array in the struct is the id field. No tool caught this. Neither compiler warned with -Wall -Wextra; AddressSanitizer, UndefinedBehaviorSanitizer and Valgrind all ran it without a report, because the read stays inside the struct, which is valid memory. Only a test that searches for a value stored just after the array would notice.
The same search on a copy in its own heap block reads past the end of the allocation, and there the tools do catch it. AddressSanitizer stops the program (reports on this page are summarized to the error, the access and the source lines):
AddressSanitizer: heap-buffer-overflow
READ of size 4 at off_by_one.c:19 in search, called from off_by_one.c:32
0 bytes after a 20-byte block allocated at off_by_one.c:28
Valgrind reported the same Invalid read of size 4 at off_by_one.c:19. GCC 13.3 noticed it only at -O3, and only indirectly, as off_by_one.c:19:14: warning: 'copy[5]' may be used uninitialized [-Wmaybe-uninitialized].
2. Reading input without checking scanf
Interactive search programs often read numbers until the user types 0, with a loop like do { scanf("%d", &value); ... } while (value != 0);. scanf returns how many values it converted, and when the input holds something that is not a number, it converts nothing, leaves the bad text unread, and leaves value unchanged:
/* unchecked_scanf.c - reading numbers until a 0 without checking what
* scanf returns. Given "5 7 x 0", scanf stops at the x and leaves it in the
* input, so the 0 is never read. The loop is capped at 10 rounds here;
* without the cap it would never end. */
#include <stdio.h>
int main(void)
{
int value = 0, rounds = 0, sum = 0;
do {
scanf("%d", &value); /* return value ignored */
sum += value;
rounds++;
} while (value != 0 && rounds < 10);
printf("rounds: %d, last value: %d, sum: %d\n", rounds, value, sum);
return 0;
}
Given the input 5 7 x 0:
rounds: 10, last value: 7, sum: 68
After reading 5 and 7, every call stops at the x, so the 0 is never reached and the 7 is counted again and again; without the cap, the loop never ends. If the very first token were bad, value would never have been set at all, which is why it is initialized here. On Ubuntu, GCC 13.3 warned from -O1 up: unchecked_scanf.c:11:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result], because Ubuntu’s GCC enables _FORTIFY_SOURCE when optimizing. At -O0, and with Clang 18 at any level, there was no warning. The fix is to check the result (if (scanf("%d", &value) != 1)) or, better, to read lines with fgets and convert them with strtol, as search_numbers does.
3. Comparing strings with ==
In C, == on two char * compares the addresses, not the text. A search written that way can even pass a quick test:
/* string_equals.c - searching an array of strings with == instead of
* strcmp. == compares addresses, so it finds a key that happens to be the
* same string literal and misses the same text typed in by a user. */
#include <stdio.h>
#include <string.h>
static const char *const fruits[] = {"apple", "banana", "cherry"};
static int search_eq(const char *key)
{
for (int i = 0; i < 3; i++)
if (fruits[i] == key) /* compares pointers */
return i;
return -1;
}
static int search_strcmp(const char *key)
{
for (int i = 0; i < 3; i++)
if (strcmp(fruits[i], key) == 0)
return i;
return -1;
}
int main(void)
{
char typed[16];
strcpy(typed, "banana"); /* as if read with fgets */
printf("== with the literal \"banana\": %d\n", search_eq("banana"));
printf("== with typed text \"banana\": %d\n", search_eq(typed));
printf("strcmp with typed text \"banana\": %d\n", search_strcmp(typed));
return 0;
}
Output:
== with the literal "banana": 1
== with typed text "banana": -1
strcmp with typed text "banana": 1
The search with == found the literal "banana", because GCC and Clang stored the two identical literals once, so the key and the array element were the same pointer. The same text in a buffer, as it would be after reading input, was not found. Neither compiler warned with -Wall -Wextra, since comparing two pointers is legal. Use strcmp(a, b) == 0 in C; in C++, std::string compares by content.
Checking the tests with deliberate mistakes
tests/mutations.py puts each of nine plausible mistakes into a copy of linear_search.c, builds the tests against it with AddressSanitizer and UndefinedBehaviorSanitizer, and records how they fail. One further change is harmless and must pass:
mistake result
loop runs one element too far (i <= n) caught: AddressSanitizer: SEGV in linear_search (linear_search.c:7)
sentinel never removed caught: FAILED line 64: one element, sentinel
sentinel taken for a real match caught: FAILED line 64: one element, sentinel
search_first steps one byte at a time caught: UBSan at test_linear_search.c:54: load of misaligned address
move-to-front shifts in the wrong direction caught: FAILED line 109: move_to_front order n=43
transpose overwrites instead of swapping caught: FAILED line 122: transpose order n=54
binary search never moves past mid caught: the tests did not finish in 30 s
binary search finds the last match, not the first caught: FAILED line 66: first of duplicates
binary search ignores the last element caught: AddressSanitizer: SEGV in binary_search (linear_search.c:63)
binary search midpoint as (lo + hi) / 2 passes: still correct
mistakes the tests miss: 0
Every mistake was caught, five by the tests’ own checks and four by the sanitizers or a timeout. The off-by-one loop, mistake 1 above, is caught at once by the empty-array test, where reading one element too far dereferences a null pointer.
Key Takeaways
- Linear search checks elements in order until it finds the key: O(n), about (n + 1) / 2 comparisons on average for a key that is present, n for one that is not. Measured: 50.49 against a predicted 50.50.
- It needs no sorting and works on any sequence, including linked lists and searches by condition, which is why
std::find_ifand genericvoid *searches exist. - For small sorted arrays it can beat binary search: faster up to 128 ints here, slower from 256, and 10 times slower at 4,096.
- The sentinel trick saved at most about 12 percent here, and not consistently, and it costs a write to the array on every search.
- Move-to-front and transpose adapt to popular keys: with Zipf traffic, transpose reached 19.71 comparisons against 19.28 for the best fixed order.
- An off-by-one read inside a struct went unnoticed by every tool; only a test can catch it.
Conclusion
Linear search is the first algorithm most programmers write and the one they are taught to replace. The measurements here argue for a more careful view: it was the faster choice up to 128 elements in these measurements, the only choice for unsorted data, and, with move-to-front or transpose, it can adapt to the keys people actually ask for.
The loop itself is four lines. The work is in the surroundings: a bound of i < n that a test actually checks, input read with its return values checked, strings compared by content, and a benchmark run before replacing it with something cleverer. More searching and sorting algorithms, measured the same way, are in the algorithms section.
Source Code and Tests
All programs on this page are in the searching/linear-search directory of the MYCPLUS C and C++ examples repositories:
| Language | Repository directory | Build |
|---|---|---|
| C | mycplus/c-examples › searching/linear-search | |
| C++ | mycplus/cpp-examples › searching/linear-search |
Build and test either one:
cmake -S . -B build
cmake --build build
ctest --test-dir build --output-on-failure
What the build checks. The C version compiles with GCC and Clang under C11 and C17 and with MSVC /W4 /WX; the C++ version with g++ and clang++ under C++17 and C++20 and with MSVC /W4 /WX /permissive-; warnings are errors, except in the three pitfall programs, whose warnings are part of the lesson. Both check every function against a reference on 20,000 random arrays, and both print exactly the outputs on this page; on Linux the C version is also compared with lfind(). The Linux workflows run everything under AddressSanitizer and UndefinedBehaviorSanitizer, and the C workflow also checks that the off-by-one read on the heap is caught and that each mutation is caught. They do not run the timing benchmark, whose figures came from one machine.
What I Verified
Each example directory contains run_all.sh for Ubuntu and WSL and run_all.ps1 for Windows, which run every check below and print one line per row.
| Check | Ubuntu 24.04 | WSL (Ubuntu) | Windows (MSVC) |
|---|---|---|---|
| C: build and CTest, GCC 13.3 and Clang 18.1.3, C11 and C17 | Pass (9 of 9 tests) | Pass (9 of 9 tests) | Not applicable |
C: build with MSVC /W4 /WX and CTest | Not applicable | Not applicable | Pass (8 of 8 tests) |
| C: 20,000 random arrays and edge cases | Pass (0 failed) | Pass | Pass |
C: agrees with lfind(), 10,000 arrays | Pass (10,000 of 10,000) | Pass | Not applicable |
| C: AddressSanitizer and UndefinedBehaviorSanitizer | Pass (GCC) | Pass (GCC) | Not applicable |
| C: Valgrind on the test suite | Pass (0 errors, no leaks) | Pass | Not applicable |
| C: off-by-one heap read caught by AddressSanitizer | Pass | Pass | Not applicable |
| C: nine mutations caught, one harmless change passes | Pass | Pass | Not applicable |
| C++: build and CTest, g++ and clang++, C++17 and C++20 | Pass (2 of 2 tests) | Pass | Not applicable |
C++: build with MSVC /W4 /WX /permissive- and CTest | Not applicable | Not applicable | Pass (2 of 2 tests) |
| C++: AddressSanitizer, UBSan and Valgrind | Pass | Pass | Not applicable |
| Benchmark | Run on the cloud VM, figures above | Not run | Not run |
Not covered: 32-bit builds, compilers newer than GCC 13.3 and Clang 18.1.3, Clang’s sanitizers on the test machine (they run in CI), timing on any other machine or compiler, and SIMD versions of linear search, which compare several elements per instruction.




