C Binary Search

Summary: in this tutorial, you will learn how to implement the C binary search algorithm. We will show you how to implement the binary search algorithm using recursion and iteration techniques.

Introduction to the binary search algorithm

Binary search is used to find the position of a key in a sorted array. The following describes the binary search algorithm:

• We compare the key with the value in the middle of the array. If the key match found, we return its position, which is the index of the middle element of the array.
• If the key is less than the value of the middle element of the array, we repeat the above step on the sub-array on the left. If the key is greater than the value of the middle element of the array, we repeat the above step on the sub-array on the right.
• If the sub-array to be searched has zero item, it means the key cannot be found.

The binary search technique performs searches on each half of the array in each step, therefore, it is known as half-interval search.

C binary search implementation

Notice that the following code is just a demonstration of implementing the binary search algorithm in C. If you want to use the binary search function, use the C bsearch() built-in function.

We can implement the binary search algorithm in C using recursion and iteration techniques.

C binary search using recursion technique

int binary_search(int sorted_list[], int low, int high, int element)
{
    if (high < low)
        return -1;
    int middle = low + (high - low)/2;
    if (element < sorted_list[middle])
        return binary_search(sorted_list, low, middle-1, element);
    else if (element > sorted_list[middle])
        return binary_search(sorted_list, middle+1, high, element);
    else
        return middle;
}
Code language: C++ (cpp)

C binary search using iteration technique

int binary_search(int sorted_list[], int low, int high, int element)
{
    int middle;
    while (low <= high)
    {
        middle = low + (high - low)/2;
        if (element > sorted_list[middle])
            low = middle + 1;
        else if (element < sorted_list[middle])
            high = middle - 1;
        else
            return middle;
    }
    return -1;
}
Code language: C++ (cpp)

We can write a program to test our binary search functions:

#include <stdio.h>
#include <stdlib.h>

#define SIZE 10
int binary_search(int sorted_list[], int low, int high, int element);

int main()
{
    int a[SIZE] = {5, 7, 8, 9 , 20, 21, 54, 67, 89, 93};
    int i, e, k, p;

    printf("Array: ");
    for(i = 0; i < SIZE; i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");

    printf("\nPlease enter the searched key:");
    scanf("%d",&k);

    p = binary_search(a,0,SIZE,k);

    if(p >= 0)
    {
        printf("The key %d was found at %d (starting from 0)",k,p);
    }
    else
    {
        printf("The key %d was not found",k);
    }
    return 0;
}

int binary_search(int sorted_list[], int low, int high, int element)
{
    int middle;
    while (low <= high)
    {
        middle = low + (high - low)/2;
        if (element > sorted_list[middle])
            low = middle + 1;
        else if (element < sorted_list[middle])
            high = middle - 1;
        else
            return middle;
    }
    return -1;
}
Code language: C++ (cpp)

The following is the output of the program:

Array: 5 7 8 9 20 21 54 67 89 93

Please enter the searched key:20
The key 20 was found at 4 (starting from 0)

In this tutorial, we have shown you how to implement binary search in C using recursion and iteration techniques.