C Program for Binary Search with Example and Explanation

A C program for binary search uses a loop to repeatedly divide the sorted array in half and compare the middle element with the target using while and if statements; for example, int binarySearch(int arr[], int n, int x) { int low=0, high=n-1; while(low<=high) { int mid=low+(high-low)/2; if(arr[mid]==x) return mid; else if(arr[mid].

Examples

Inputarr = {2, 4, 6, 8, 10}, x = 6

OutputElement found at index 2

Inputarr = {1, 3, 5, 7, 9}, x = 4

OutputElement not found in the array

Inputarr = {10, 20, 30, 40, 50}, x = 10

OutputElement found at index 0

How to Think About It

To perform binary search, first ensure the array is sorted. Then, repeatedly check the middle element of the current search range. If it matches the target, return its position. If the target is smaller, search the left half; if larger, search the right half. Continue until the element is found or the range is empty.

Algorithm

1

Start with low = 0 and high = last index of the array.

2

While low is less than or equal to high:

3

Calculate mid as the average of low and high.

4

If the element at mid equals the target, return mid.

5

If the element at mid is less than the target, set low to mid + 1.

6

Else, set high to mid - 1.

7

If the element is not found, return -1.

Code

c

#include <stdio.h>

int binarySearch(int arr[], int n, int x) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == x)
            return mid;
        else if (arr[mid] < x)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 6;
    int result = binarySearch(arr, n, x);
    if (result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found in the array\n");
    return 0;
}

Output

Element found at index 2

Dry Run

Let's trace searching for 6 in the array {2, 4, 6, 8, 10} using binary search.

1

Initialize pointers

low = 0, high = 4 (array indices)

2

Calculate mid

mid = 0 + (4 - 0) / 2 = 2

3

Compare mid element

arr[2] = 6 equals target 6, return index 2

low	high	mid	arr[mid]	comparison
0	4	2	6	6 == 6, found

Why This Works

Step 1: Divide and conquer

Binary search works by dividing the search range in half each time, reducing the problem size quickly.

Step 2: Middle element check

Checking the middle element lets us decide which half to keep searching, because the array is sorted.

Step 3: Adjust search range

If the middle element is less than the target, we search the right half; if more, the left half.

Step 4: Stop condition

When low exceeds high, the target is not in the array, so we return -1.

Alternative Approaches

Recursive binary search

c

#include <stdio.h>

int binarySearchRecursive(int arr[], int low, int high, int x) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (arr[mid] == x) return mid;
    else if (arr[mid] < x) return binarySearchRecursive(arr, mid + 1, high, x);
    else return binarySearchRecursive(arr, low, mid - 1, x);
}

int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 6;
    int result = binarySearchRecursive(arr, 0, n - 1, x);
    if (result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found in the array\n");
    return 0;
}

Uses recursion instead of a loop; easier to read but uses more stack memory.

Linear search

c

#include <stdio.h>

int linearSearch(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) return i;
    }
    return -1;
}

int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 6;
    int result = linearSearch(arr, n, x);
    if (result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found in the array\n");
    return 0;
}

Checks each element one by one; simple but slower for large arrays.

Complexity: O(log n) time, O(1) space

Time Complexity

Binary search divides the search space in half each step, so it runs in logarithmic time, O(log n).

Space Complexity

The iterative version uses constant extra space, O(1), as it only stores a few variables.

Which Approach is Fastest?

Iterative binary search is fastest and uses less memory than recursive; linear search is slower but simpler.

Approach	Time	Space	Best For
Iterative Binary Search	O(log n)	O(1)	Large sorted arrays, memory efficient
Recursive Binary Search	O(log n)	O(log n)	Readable code, small arrays
Linear Search	O(n)	O(1)	Unsorted or small arrays