</>EmbeddedInterview
← All problems · Arrays & Searching

Binary Search in a Sorted Array

Easy

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) / 2 can overflow when indexes are large; low + (high - low) / 2 cannot.
  • Mixing inclusive and exclusive bounds: with high = n - 1 the loop is low <= high and the update is high = mid - 1. With high = n it is low < high and high = mid. Mixing them causes infinite loops or missed elements.
  • Hard-coding the size (high = 6) instead of using n.

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.

solution.c
OutputPress Run to compile and test your code.
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;
}