Linear and binary search

A search answers one question: where is this value, or why is it absent. Linear search works on any array and looks at each element once. Binary search is faster but needs the array sorted first, and it is easy to get the boundary wrong by one index. The sorts of lessons 47 and 48 supply that order.

Linear search

Linear search returns the index of the first match, or -1 when the array has no such value. The return type is the index, not the value, so -1 is free to mean "not found" as long as the caller treats it as an index. The loop stops at the first match, which makes the order of duplicates visible.

#include <stdio.h> static int find(const int *values, int count, int key) { for (int i = 0; i < count; i++) { if (values[i] == key) { return i; } } return -1; } int main(void) { int values[6] = {4, 8, 15, 16, 23, 42}; printf("23 at %d\n", find(values, 6, 23)); printf("7 at %d\n", find(values, 6, 7)); return 0; }

gcc -Wall -Wextra linear.c -o linear
./linear

23 at 4
7 at -1

23 is the fifth element, so its index is 4. The missing value returns -1, which an array index can never be, and the caller must check that before using the result. On an unsorted array this is the only search that works without extra preparation.

Binary search

Binary search halves the range on every step: compare the middle element with the key and keep the half that can contain it. The loop ends when the range is empty. The middle is computed as low + (high - low) / 2 so that adding the two bounds cannot overflow.

#include <stdio.h> static int find(const int *values, int count, int key) { int low = 0; int high = count - 1; while (low <= high) { int middle = low + (high - low) / 2; if (values[middle] == key) { return middle; } if (values[middle] < key) { low = middle + 1; } else { high = middle - 1; } } return -1; } int main(void) { int values[6] = {4, 8, 15, 16, 23, 42}; printf("23 at %d\n", find(values, 6, 23)); printf("4 at %d\n", find(values, 6, 4)); printf("7 at %d\n", find(values, 6, 7)); return 0; }

gcc -Wall -Wextra binary.c -o binary
./binary

23 at 4
4 at 0
7 at -1

Four is found on the first comparison because it is the middle of the range. Seven ends with low greater than high, which is the loop's "not found" condition. The array must be sorted; on an unsorted array the halving discards the half that could contain the key.

The first occurrence

With duplicates, the plain binary search returns some match, not necessarily the first one. A lower-bound search keeps the range open and moves high to the middle even when the values are equal, so it ends at the first element that is not smaller than the key. That position is also where the key would be inserted.

#include <stdio.h> static int first_at_least(const int *values, int count, int key) { int low = 0; int high = count; while (low < high) { int middle = low + (high - low) / 2; if (values[middle] < key) { low = middle + 1; } else { high = middle; } } return low; } int main(void) { int values[9] = {1, 3, 3, 3, 5, 7, 7, 9, 11}; printf("first 3 at %d\n", first_at_least(values, 9, 3)); printf("first 7 at %d\n", first_at_least(values, 9, 7)); printf("first 4 at %d\n", first_at_least(values, 9, 4)); return 0; }

gcc -Wall -Wextra first.c -o first
./first

first 3 at 1
first 7 at 5
first 4 at 4

The key 4 is not present, and the function returns 4, the index where it would be inserted to keep the array sorted. The count of occurrences is then first_at_least(key + 1) - first_at_least(key), which is two searches over the same array.

How many steps

Counting iterations shows the difference. On sixteen elements a linear search for the last value takes sixteen comparisons, while binary search takes five, because two to the fifth is thirty-two. The gap grows with the logarithm, which is why a sorted array is worth the sort when the same data is searched many times.

#include <stdio.h> static int linear_steps(const int *values, int count, int key) { int steps = 0; for (int i = 0; i < count; i++) { steps++; if (values[i] == key) { return steps; } } return steps; } static int binary_steps(const int *values, int count, int key) { int low = 0; int high = count - 1; int steps = 0; while (low <= high) { int middle = low + (high - low) / 2; steps++; if (values[middle] == key) { return steps; } if (values[middle] < key) { low = middle + 1; } else { high = middle - 1; } } return steps; } int main(void) { int values[16] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}; printf("linear: %d\n", linear_steps(values, 16, 16)); printf("binary: %d\n", binary_steps(values, 16, 16)); return 0; }

gcc -Wall -Wextra steps.c -o steps
./steps

linear: 16
binary: 5

The first middle is 7, then 11, then 13, then 15, then 16: five steps for sixteen elements. Doubling the array adds one step, not sixteen, which is the whole point of the halving.

Overflow and a stuck bound

The midpoint formula (low + high) / 2 overflows when both bounds are near the top of the int range. The sanitizer reports the exact sum, and the wrong sign shows in the printed result:

#include <limits.h> #include <stdio.h> int main(void) { int low = INT_MAX - 1; int high = INT_MAX; int middle = (low + high) / 2; printf("%d\n", middle); return 0; }

gcc -fsanitize=undefined -g -Wall -Wextra midpoint.c -o midpoint
./midpoint; echo "exit: $?"

midpoint.c:8:23: runtime error: signed integer overflow: 2147483646 + 2147483647 cannot be represented in type 'int'
-1
exit: 0

The sum wraps to a negative number, so the division returns -1 and the search would look before the array. The subtraction form low + (high - low) / 2 used in this lesson cannot overflow, because both bounds are non-negative and the difference fits.

The second mistake is a bound that never moves. Setting high = middle instead of high = middle - 1 leaves the same range when the key is not found, so the loop never ends:

#include <stdio.h> static int find(const int *values, int count, int key) { int low = 0; int high = count - 1; while (low <= high) { int middle = low + (high - low) / 2; if (values[middle] == key) { return middle; } if (values[middle] < key) { low = middle + 1; } else { high = middle; } } return -1; } int main(void) { int values[4] = {1, 3, 5, 7}; printf("%d\n", find(values, 4, 4)); return 0; }

gcc -Wall -Wextra loop.c -o loop
timeout 2 ./loop; echo "exit: $?"

exit: 124

124 is the status timeout reports when it stopped the program after two seconds. The search for 4 keeps asking the same middle, because high lands on it and never moves below. The correct bound shrinks the range on both sides.

Exercises

  1. Write a linear search that returns the last occurrence of a key instead of the first.
  2. Use first_at_least twice to count how many times the value 3 appears in the example array.
  3. Run binary search on an array that is not sorted and describe the first wrong answer it gives.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does a linear search return when the key is absent?

    Answer

    -1, a value no valid index can have

    A valid index is at least zero, so -1 is free to mean that no element matched.

  2. What must be true before binary search can work?

    Answer

    The array must already be sorted

    The halving discards half the range on the assumption that the order tells which half can contain the key.

  3. What does a lower-bound search return for a missing key?

    Answer

    The index where the key would be inserted

    The loop ends at the first element not smaller than the key, which is also the insertion point.

  4. Why is the range kept as [low, high) in the lower-bound search?

    Answer

    It makes high = middle shrink the range

    With an open upper bound, moving high to middle still makes progress, and the final low is the answer.

  5. What does this program print? #include <stdio.h> static int find(const int*v,int n,int k){int l=0,h=n-1;while(l<=h){int m=l+(h-l)/2;if(v[m]==k)return m;if(v[m]<k)l=m+1;else h=m-1;}return -1;} int main(void){int v[6]={4,8,15,16,23,42};printf("%d %d %d\n",find(v,6,23),find(v,6,4),find(v,6,7));return 0;}

    Answer

    4 0 -1

    23 is at index 4, 4 at index 0, and the missing 7 returns -1.

  6. What does this program print? #include <stdio.h> static int first(const int*v,int n,int k){int l=0,h=n;while(l<h){int m=l+(h-l)/2;if(v[m]<k)l=m+1;else h=m;}return l;} int main(void){int v[9]={1,3,3,3,5,7,7,9,11};printf("%d %d %d\n",first(v,9,3),first(v,9,7),first(v,9,4));return 0;}

    Answer

    1 5 4

    The first 3 is at index 1, the first 7 at index 5, and 4 would be inserted at index 4.

  7. How many steps do the two searches take for the last of sixteen values?

    Answer

    linear 16 and binary 5

    Linear search checks every element, while the halving takes five steps to reach the sixteenth value.

  8. Why is low + (high - low) / 2 safer than (low + high) / 2 for the midpoint?

    Answer

    The subtraction cannot overflow the int range

    Both bounds are non-negative, so their difference fits even when their sum would overflow.

  9. What happens when a binary search sets high = middle and never middle - 1?

    Answer

    The same range repeats and the loop never ends

    When the key is below the middle, the upper bound lands on the same middle again, so the range does not shrink.

  10. Why does binary search fail on an unsorted array?

    Answer

    The halving discards the half that holds the key

    The decision to keep one half assumes the order, so on unsorted data the key can be in the half that is thrown away.

The code on this page was run with gcc (Alpine 15.2.0) 15.2.0 on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev

Banner image