typestar

Binary search in C

Halve the range each step; a thousand items takes ten comparisons.

int binary_search(const int *items, int n, int target) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (items[mid] == target)
            return mid;
        if (items[mid] < target)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
    return -1;
}

Keywords and builtins used here

The run, in numbers

Lines
13
Characters to type
240
Tokens
87
Three-star pace
95 tpm

At the three-star pace of 95 tokens a minute, this run takes about 55 seconds.

Type this snippet

Step 3 of 5 in Sorting & searching, step 3 of 20 in Data structures & algorithms.

← Previous Next →

Binary search in other languages