C program to implement binary search using recursion

Here, we are going to learn how to implement binary search using recursion in C language?
Submitted by Nidhi, on August 26, 2021

Problem Solution:

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

Program:

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:

Enter item to search: 75
Item found at index 4

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.

Top MCQs

Comments and Discussions!