C program to implement binary search using recursion

In this tutorial, we will learn how to implement binary search using recursion in C language? By Nidhi Last updated : August 10, 2023

Problem statement

Create an array of integers, then implement binary search using recursion and print the index of the item.

C program to implement binary search using recursion

The source code to implement binary search using recursion is given below. The given program is compiled and executed using GCC compile on UBUNTU 18.04 OS successfully.

// C program to implement binary search
// using the recursion

#include <stdio.h>

int binarySearch(int arr[], int lo, int hi, int item)
{
    int mid;

    if (lo > hi)
        return -1;

    mid = (lo + hi) / 2;

    if (arr[mid] == item)
        return mid;
    else if (arr[mid] > item)
        binarySearch(arr, lo, mid - 1, item);
    else if (arr[mid] < item)
        binarySearch(arr, mid + 1, hi, item);
}

int main()
{
    int arr[] = { 10, 21, 23, 46, 75 };
    int index = 0;
    int item = 0;

    printf("Enter item to search: ");
    scanf("%d", &item);

    index = binarySearch(arr, 0, 5, item);
    if (index == -1)
        printf("Item not found in array\n");
    else
        printf("Item found at index %d\n", index);

    return 0;
}

Output

RUN 1:
Enter item to search: 75
Item found at index 4

RUN 2:
Enter item to search: 10
Item found at index 0

RUN 3:
Enter item to search: 99
Item not found in array

Explanation

Here, we created two functions binarySearch() and main(). The binarySearch() is a recursive function, which is used to search an item in the sorted array and return the index of the item to the calling function.

In the main() function, we created an array of integers arr with 5 elements. Then we implemented the binary search using recursion and printed the index of the item in the array.