Binary Search in a Sorted Array
Implement int binary_search(const int *a, int n, int target) that returns the index of target in an array sorted ascending, or -1 if it is not present. Use O(log n) comparisons and no recursion.
Example: {2, 4, 6, 8, 10, 12, 14}, target 12 → 5.
Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.
Keep an inclusive range [low, high]. Compare the target with the middle element and discard the half that cannot contain it. Compute the middle without overflowing.
#include <stdio.h>
int binary_search(const int *a, int n, int target)
{
int low = 0, high = n - 1; /* inclusive range */
while (low <= high) {
int mid = low + (high - low) / 2; /* no overflow */
if (a[mid] == target)
return mid;
if (target < a[mid])
high = mid - 1; /* search left half */
else
low = mid + 1; /* search right half */
}
return -1;
}
Each comparison halves the search range, so at most ⌈log₂(n+1)⌉ comparisons are needed: 20 for a million elements. O(log n) time, O(1) memory. The array must be sorted.
Walk-through: {2, 4, 6, 8, 10, 12, 14}, target 12
| low | high | mid | a[mid] | action |
|---|---|---|---|---|
| 0 | 6 | 3 | 8 | 12 > 8 → low = 4 |
| 4 | 6 | 5 | 12 | found at 5 |
The bugs interviewers look for:
mid = (low + high) / 2can overflow when indexes are large;low + (high - low) / 2cannot.- Mixing inclusive and exclusive bounds: with
high = n - 1the loop islow <= highand the update ishigh = mid - 1. Withhigh = nit islow < highandhigh = mid. Mixing them causes infinite loops or missed elements. - Hard-coding the size (
high = 6) instead of usingn.
Follow-ups: find the first or last occurrence of a duplicated value (keep searching after a match); the insertion point (lower bound); search a rotated sorted array; binary search on the answer (e.g. the smallest baud-rate divisor that meets an error limit). In firmware, binary search is used on calibration and lookup tables in flash; see Calibration Table Interpolation.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
int main(void)
{
const int a[] = { 2, 4, 6, 8, 10, 12, 14 };
CHECK(binary_search(a, 7, 12) == 5);
CHECK(binary_search(a, 7, 2) == 0); /* first */
CHECK(binary_search(a, 7, 14) == 6); /* last */
CHECK(binary_search(a, 7, 1) == -1); /* below range */
CHECK(binary_search(a, 7, 15) == -1); /* above range */
CHECK(binary_search(a, 7, 7) == -1); /* gap */
CHECK(binary_search(a, 0, 2) == -1); /* empty */
const int one[] = { 5 };
CHECK(binary_search(one, 1, 5) == 0);
for (int i = 0; i < 7; i++) CHECK(binary_search(a, 7, a[i]) == i);
puts(fails ? "Some tests failed" : "All tests passed");
return fails != 0;
}