Bytebook Compiler

Searching & Sorting

Linear & Binary Search

Find things fast: linear search for any list, binary search for sorted ones — iterative and recursive versions, step-by-step traces and the classic off-by-one traps.

5 min read3 runnable examplesInteractive4-question quiz

Check every element from the start until you find the key. It works on any list, sorted or not.

  • Best case O(1), worst and average case O(n).

You wrote it in the Arrays lesson. Its weakness is speed on large data.

If the array is sorted, you can do much better. Look at the middle element:

  • equal to the key → found;
  • key smaller → the key can only be in the left half;
  • key larger → it can only be in the right half.

Each step halves the search space, so at most about log₂ n steps are needed: O(log n). For a million elements that is 20 comparisons instead of a million.

C
#include <stdio.h>

int binarySearch(const int a[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;     // avoids overflow of (low + high)
        printf("  low=%d high=%d mid=%d a[mid]=%d\n", low, high, mid, a[mid]);
        if (a[mid] == key) return mid;
        if (a[mid] < key) low = mid + 1;       // key is in the right half
        else high = mid - 1;                   // key is in the left half
    }
    return -1;
}

int main(void) {
    int a[] = {3, 8, 15, 21, 29, 34, 42, 57, 63, 78};
    int n = 10;
    printf("search 57:\n");
    printf("-> index %d\n", binarySearch(a, n, 57));
    printf("search 10:\n");
    printf("-> index %d\n", binarySearch(a, n, 10));
    return 0;
}
Output
search 57:
  low=0 high=9 mid=4 a[mid]=29
  low=5 high=9 mid=7 a[mid]=57
-> index 7
search 10:
  low=0 high=9 mid=4 a[mid]=29
  low=0 high=3 mid=1 a[mid]=8
  low=2 high=3 mid=2 a[mid]=15
-> index -1
Try it Yourself
3081152213294345426577638789lowmidhigh
Second step of the search for 57: the left half was discarded, and mid now lands on 57.
C
#include <stdio.h>

int bs(const int a[], int low, int high, int key) {
    if (low > high) return -1;                       // empty range: not found
    int mid = low + (high - low) / 2;
    if (a[mid] == key) return mid;
    return a[mid] < key ? bs(a, mid + 1, high, key) : bs(a, low, mid - 1, key);
}

int main(void) {
    int a[] = {2, 4, 7, 10, 23, 38, 56, 72, 91};
    int keys[] = {23, 2, 91, 50};
    for (int i = 0; i < 4; i++) printf("%d -> %d\n", keys[i], bs(a, 0, 8, keys[i]));
    return 0;
}
Output
23 -> 4
2 -> 0
91 -> 8
50 -> -1
Try it Yourself

Recurrence: T(n) = T(n/2) + O(1) → O(log n). The recursive version uses O(log n) stack space; the iterative one uses O(1).

Variants worth knowing

Binary search finds more than exact matches. Changing what happens on equality gives you the first or last occurrence of a repeated key:

C
#include <stdio.h>

int firstOccurrence(const int a[], int n, int key) {
    int low = 0, high = n - 1, ans = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == key) { ans = mid; high = mid - 1; }   // record it, keep looking left
        else if (a[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return ans;
}

int lastOccurrence(const int a[], int n, int key) {
    int low = 0, high = n - 1, ans = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == key) { ans = mid; low = mid + 1; }    // keep looking right
        else if (a[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return ans;
}

int main(void) {
    int a[] = {1, 3, 3, 3, 3, 5, 8, 8, 9};
    int f = firstOccurrence(a, 9, 3), l = lastOccurrence(a, 9, 3);
    printf("3 appears from index %d to %d: %d times\n", f, l, l - f + 1);
    return 0;
}
Output
3 appears from index 1 to 4: 4 times
Try it Yourself
Linear search Binary search
Needs sorted data no yes
Time O(n) O(log n)
Works on linked lists yes not efficiently (no random access)

Test yourself

4 questions · pick an answer to check it instantly

  1. 1

    What is the precondition for binary search?

  2. 2

    How many comparisons does binary search need, at most, for 1,024 elements?

  3. 3

    Searching for 15 in [3, 8, 15, 21, 29]: what is the first mid index?

  4. 4

    Why write mid = low + (high - low) / 2?

Esc
↑↓ move↵ open