Binary Search in C

Algorithm

1. Read n and the n integers, which must already be in ascending order.
2. Read the key to search for.
3. Set low to 0 and high to n - 1.
4. While low is not greater than high, compute mid = low + (high - low) / 2.
5. If the element at mid equals the key, return mid; if the key is smaller, set high = mid - 1; otherwise set low = mid + 1.
6. If the loop ends without a match, the key is not present.

C program

#include <stdio.h>

#define MAX_SIZE 100

int binary_search(const int arr[], int n, int key) {
    int low = 0;
    int high = n - 1;
    int mid;

    while (low <= high) {
        mid = low + (high - low) / 2;
        if (arr[mid] == key) {
            return mid;
        }
        if (key < arr[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

int main(void) {
    int arr[MAX_SIZE];
    int n, i, key, pos;

    printf("Enter number of elements (1-%d):\n", MAX_SIZE);
    if (scanf("%d", &n) != 1 || n < 1 || n > MAX_SIZE) {
        printf("Error: invalid size\n");
        return 1;
    }

    printf("Enter %d elements in ascending order:\n", n);
    for (i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    printf("Enter key to search:\n");
    scanf("%d", &key);

    pos = binary_search(arr, n, key);
    if (pos >= 0) {
        printf("Element %d found at position %d (1-based)\n", key, pos + 1);
    } else {
        printf("Element %d not found\n", key);
    }
    return 0;
}

Sample input and output

7
2 5 8 12 16 23 38
23

Enter number of elements (1-100):
Enter 7 elements in ascending order:
Enter key to search:
Element 23 found at position 6 (1-based)

7
2 5 8 12 16 23 38
1

Enter number of elements (1-100):
Enter 7 elements in ascending order:
Enter key to search:
Element 1 not found

How the program works

Binary search works only on sorted data. Each comparison with the middle element discards the half of the range that cannot contain the key, so a list of n items needs at most about log2(n) + 1 comparisons.

mid is computed as low + (high - low) / 2 rather than (low + high) / 2. The two are equal in value, but the first form cannot overflow when low and high are both large.

Viva questions

Common mistakes

• Running binary search on an unsorted array and reporting wrong results.
• Setting high = mid instead of mid - 1, which can loop forever when the key is absent.
• Printing the 0-based index without converting it to a position, which confuses users who count from 1.