Linear Search vs Binary Search vs HashSet, Measured

Revised November 2026. This tutorial first appeared in Korean in 2021. We recompiled its two C examples with Apple clang 21 (-Wall -Wextra -fsanitize=address,undefined). Neither compiled as C (undeclared true, missing struct tag), and the linked-list example printed 64-bit pointers with %#x, which showed only the low 32 bits of each address. Below are the fixes, the sentinel and early-exit variants, and measurements on .NET 10 comparing linear search, binary search and HashSet<int> from 100 to 1 million elements.

This article is for developers who want a number, not a rule of thumb, for "when should I stop scanning the array and use something smarter?" The short answer: for one or two lookups, linear search is right, and in C# the built-in Span.IndexOf was more than three times faster than a hand-written loop. For repeated lookups on the same data, binary search won from roughly 500 elements against the vectorized scan, and HashSet<T> stayed at 4 to 5 ns regardless of size.

What linear search is

Sequential search, more often called linear search, compares each element from the first to the last until it finds the target. It needs no preprocessing, works on unsorted data and on linked lists, and its cost grows in proportion to the number of elements: O(n).

The 2021 post said the average is (n+1)/2 comparisons. That holds only when the target is present and equally likely to be anywhere. When it is absent, every one of the n elements is compared. In real code, lookups for missing values are common, so plan for n.

Re-compiling the 2021 examples

The array example used while (true) without including <stdbool.h>. In clang's default C mode (gnu17) that fails:

seq2021a.c:16:12: error: use of undeclared identifier 'true'
   16 |     while (true)
      |            ^~~~
1 error generated.

It compiles with -std=c23 (where true became a keyword) or as C++, but running it shows a second problem: the loop never ends. Once input runs out, scanf fails, the old value stays in the variable, and the program searches for it forever (output translated from Korean):

Enter a value: Found at index 7.
Enter a value: Found at index 7.
Enter a value: Found at index 7.
… (never stops)

The linked-list example produced two errors and a warning as C:

seq2021b.c:6:5: error: must use 'struct' tag to refer to type 'Node'
    6 |     Node* link;
      |     ^
      |     struct 
seq2021b.c:59:12: error: use of undeclared identifier 'true'
seq2021b.c:65:72: warning: format specifies type 'unsigned int' but the argument has type 'Node *' (aka 'struct Node *') [-Wformat]

Inside the struct body, the typedef name Node does not exist yet, so C needs struct Node *link;. The 2021 code was most likely compiled as C++, where it is accepted. The %#x warning matters more. Compiled as C++ and run, the program printed a node address as 0xf0; the same node printed with %p is 0x6020000000f0. Formatting a 64-bit pointer as a 32-bit unsigned int is undefined behavior, and here it silently dropped the top bits.

The fixed version adds the struct tag, stops when input ends, prints with %p and frees the list:

typedef struct Node {
    int data;
    struct Node *link;              /* C needs the struct tag here */
} Node;

static Node *sequentialSearch(Node *head, int findData)
{
    for (Node *p = head; p != NULL; p = p->link)
        if (p->data == findData) return p;
    return NULL;
}
/* main: while (scanf("%d", &findData) == 1) { … printf("%p", (void *)found); } freeList(head); */

$ printf "54\n33\n72\n53\n" | ./list_fixed
54: not found
33: node at 0x6020000000f0
72: node at 0x602000000150
53: node at 0x602000000170

A linked list cannot be binary-searched, because there is no way to jump to the middle node, so linear search is effectively the only option there. The array example, fixed the same way with while (scanf(...) == 1), compiles as C17 with no warnings and exits at end of input.

Sentinel and early exit on sorted data

Two classic refinements exist. The sentinel technique stores the target in the last slot, so the scan is guaranteed to stop and the i < n check can be dropped from the loop. Early exit applies to data sorted in ascending order: once a[i] exceeds the target, the target cannot appear later.

/* sentinel: put the key in the last slot so the loop needs no bounds check */
static int sentinel(int *a, int n, int key)
{
    int last = a[n - 1];
    a[n - 1] = key;
    int i = 0;
    while (a[i] != key) i++;
    a[n - 1] = last;                        /* restore */
    if (i < n - 1 || last == key) return i;
    return -1;
}

/* sorted ascending: stop as soon as a[i] >= key */
static int sorted_early(const int *a, int n, int key)
{
    for (int i = 0; i < n; i++)
        if (a[i] >= key) return a[i] == key ? i : -1;
    return -1;
}

Comparisons against the key on the sorted array {5, 13, 14, 23, 25, 51, 66, 72, 224}:

key  23: linear  3 (4 cmp)  sentinel  3 (4 cmp)  sorted-early  3 (4 cmp)
key 224: linear  8 (9 cmp)  sentinel  8 (9 cmp)  sorted-early  8 (9 cmp)
key  22: linear -1 (9 cmp)  sentinel -1 (9 cmp)  sorted-early -1 (4 cmp)
key 500: linear -1 (9 cmp)  sentinel -1 (9 cmp)  sorted-early -1 (9 cmp)
key   1: linear -1 (9 cmp)  sentinel -1 (9 cmp)  sorted-early -1 (1 cmp)

Early exit helps only for missing keys (4 comparisons instead of 9 for 22). The sentinel makes the same number of key comparisons and saves only the bounds check, so we timed it: 2,000 lookups in a 1-million-int array, clang -O2, Apple M1 Pro.

round 0: plain 336.4 ms, sentinel 325.7 ms
round 1: plain 321.6 ms, sentinel 318.4 ms
round 2: plain 318.1 ms, sentinel 318.6 ms

The difference is within noise. A well-predicted i < n branch is nearly free on a current CPU. Because the sentinel writes into the array, it also cannot be used on const data or on an array other threads are reading. Today it is mostly a textbook technique.

Linear vs binary search vs HashSet: the numbers

Next, the question that matters in practice: when should you switch? Setup: .NET 10.0.14, Release build, Apple M1 Pro (Vector128.IsHardwareAccelerated = True, Vector<int>.Count = 4). The array holds sorted even numbers and every key is present, chosen at random. Each method is called through a Func<int,int> delegate, so every column carries the same few nanoseconds of call overhead. Values are the best of three runs, in nanoseconds per lookup.

[MethodImpl(MethodImplOptions.NoInlining)]
static int Naive(int[] a, int key)
{
    for (int i = 0; i < a.Length; i++)
        if (a[i] == key) return i;
    return -1;
}

double loop = Run(lookups, keys, k => Naive(a, k));
double span = Run(lookups, keys, k => a.AsSpan().IndexOf(k));
double arr  = Run(lookups, keys, k => Array.IndexOf(a, k));
double bin  = Run(lookups, keys, k => Array.BinarySearch(a, k));
double hb   = Run(lookups, keys, k => HandBinary(a, k));   // lo + ((hi - lo) >> 1)
double hs   = Run(lookups, keys, k => set.Contains(k) ? 1 : 0);

(ns per lookup. In a second run, Array.BinarySearch at 1 million moved to 205 ns; the other cells stayed within about 10%.)

To find the crossover, we swept N in finer steps:

• Plain loop vs binary search: about even at 100 elements; binary search ahead from 128.
• Span.IndexOf vs binary search: linear was as fast or faster up to 512; binary search won clearly from 768. Vectorization pushed the crossover out by roughly a factor of four.
• HashSet: 4 to 5 ns at every size. It has a build cost, though: new HashSet<int>(data) for 1 million random ints took 50-60 ms, and Array.Sort about 59 ms after JIT warm-up. One Span.IndexOf scan of 1 million ints costs about 0.046 ms, so building a sorted array or a set pays off after roughly 1,200 lookups.

The binary search implementation itself, including the midpoint overflow trap, is covered in our binary search article.

Why Span.IndexOf is over three times faster

The most striking result is that Span.IndexOf and Array.IndexOf are the same O(n) algorithm as the loop, yet ran 3.4 times faster at 10,000 elements and 3.7 times faster at 1 million. For bitwise-comparable types such as int, .NET implements IndexOf with SIMD instructions. On Apple Silicon's 128-bit NEON registers, it compares four ints at once and checks a mask for any match. A hand-written loop that returns as soon as it finds a match is not auto-vectorized by the JIT, so it compares one element at a time.

Array.IndexOf(int[], int) takes the same path internally and matched Span.IndexOf. List<int>.IndexOf and Contains call Array.IndexOf on the backing array, so they benefit too. In C# there is little reason to hand-write a linear search over primitive types. In C, our scan of 1 million ints took about 0.16 ms per lookup, close to the .NET loop (0.168 ms) and well behind Span.IndexOf (0.045 ms). Matching it in C means writing NEON or SSE intrinsics yourself; memchr works only on bytes, not on int arrays.

Choosing a lookup strategy

• One or two lookups, or a linked list: linear search. In C#, use Span.IndexOf, Array.IndexOf or Contains.
• Many lookups on the same data (about 1,200 or more at 1 million elements): the one-off cost of sorting or hashing is recovered.
• You need ordering or range queries: sort once and binary search. Below a few hundred elements, a vectorized linear scan is just as fast.
• You only need membership: HashSet<T>, flat at 4-5 ns in our test.
• The sentinel trick gave no measurable gain on a current compiler and CPU. Early exit on sorted data helps only when many lookups miss.