K&R C Exercise 3-1: Binary Search with One Comparison Per Loop

Exercise 3-1. Our binary search makes two tests inside the loop, when one would suffice (at the cost of more tests outside). Write a version with only one test inside the loop and measure the difference in run-time.

The standard K&R binsearch performs two comparisons per iteration — it checks x < v[mid], then x > v[mid], with a return mid as the third case. The one-test version moves the equality check outside the loop entirely. The loop only asks one question: “is mid too high?” using a single x <= v[mid] test, always narrowing the range to [low, mid] or [mid+1, high]. The loop condition becomes low < high (not low <= high), and high = mid (not mid - 1) — these two changes are coupled: they maintain the invariant that if the target is present, it is always within v[low..high]. After the loop, one final equality check at v[low] determines found-or-not.

Both Versions Side by Side

/* K&R Exercise 3-1 — binary search: one test inside the loop
 * Compile: gcc -ansi -Wall ex3-1.c -o ex3-1 */
#include <stdio.h>

/* Original K&R version — two tests per iteration */
int binsearch_two(int x, int v[], int n)
{
    int low, high, mid;
    low = 0;
    high = n - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (x < v[mid])
            high = mid - 1;
        else if (x > v[mid])
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

/* Exercise 3-1 — one test per iteration */
int binsearch_one(int x, int v[], int n)
{
    int low, high, mid;
    low = 0;
    high = n - 1;
    while (low < high) {
        mid = (low + high) / 2;
        if (x <= v[mid])
            high = mid;
        else
            low = mid + 1;
    }
    return (v[low] == x) ? low : -1;
}

int main(void)
{
    int v[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = 10;
    printf("Search 23: two=%d one=%d\n",
           binsearch_two(23, v, n), binsearch_one(23, v, n));
    printf("Search  1: two=%d one=%d\n",
           binsearch_two(1, v, n),  binsearch_one(1, v, n));
    printf("Search 91: two=%d one=%d\n",
           binsearch_two(91, v, n), binsearch_one(91, v, n));
    return 0;
}

Why high = mid and Not mid - 1?

In the two-test version, when x < v[mid], we know mid is too high so we set high = mid - 1. In the one-test version we do not know whether v[mid] == x yet — we only know x <= v[mid], so mid itself could be the answer. Setting high = mid keeps it in range. The loop terminates because mid = (low + high) / 2 is always strictly less than high when low < high, so the range shrinks every iteration.

Compile and Run

gcc -ansi -Wall ex3-1.c -o ex3-1
./ex3-1

Sample Output

Search 23: two=5 one=5
Search  1: two=-1 one=-1
Search 91: two=9 one=9

What This Exercise Teaches

• Loop invariant design — the one-test version maintains the invariant that the target, if present, is always within v[low..high]
• Off-by-one discipline — high = mid and low < high are coupled; changing one without the other breaks the termination proof
• Trade-off analysis — one comparison per iteration saves work inside the loop at the cost of one extra comparison after; the difference is negligible in practice
• Termination proof — (low + high) / 2 < high when low < high, guaranteeing the range shrinks every step

Set Up Your C Environment

Need GCC? Quick links:

• Install GCC on Windows 11
• Install GCC on macOS
• Install GCC on Ubuntu/Linux
• VS Code for C Programming

← Exercise 2-10  | 
Chapter 3 Solutions  | 
Exercise 3-2 →

Book:
The C Programming Language, 2nd Ed — Kernighan & Ritchie