C Binary Search Program

Binary search finds a value in a sorted array. It checks the middle element and throws away half of the array each time, so it is much faster than linear search for big arrays.

#include <stdio.h>

int binarySearch(int a[], int size, int key) {
    int low = 0, high = size - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (a[mid] == key) return mid;
        if (a[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main(void) {
    int a[] = {5, 12, 19, 27, 33, 48, 56, 71};
    int size = sizeof(a) / sizeof(a[0]);

    int pos = binarySearch(a, size, 33);
    if (pos != -1) printf("33 found at index %d\n", pos);

    pos = binarySearch(a, size, 40);
    if (pos == -1) printf("40 not found\n");
    return 0;
}

Output:

How it works

• The array must be sorted in ascending order.
• If the middle value is smaller than the key, the key can only be in the right half. Otherwise it is in the left half.
• For 8 elements it needs at most 4 steps. For 1 million elements it needs only about 20 steps.

• Previous Code
• Next Code

---

Tutorials
No Content Found.

Exercises & Assignments
No Content Found.

Interview Questions & Answers
No Content Found.