Write a C Program to implement Binary Search using Recursion

C Program to implement Binary Search


Write a C Program to implement Binary Search using Recursion.┬áHere’s simple Program to implement Binary Search using Recursion in C Programming Language.


Recursion : :


  • Recursion is the process of repeating items in a self-similar way. In programming languages, if a program allows you to call a function inside the same function, then it is called a recursive call of the function.
  • The C programming language supports recursion, i.e., a function to call itself. But while using recursion, programmers need to be careful to define an exit condition from the function, otherwise it will go into an infinite loop.
  • Recursive functions are very useful to solve many mathematical problems, such as calculating the factorial of a number, generating Fibonacci series, etc.

Problem : :


This C program, using recursion, performs binary search. In this program an array of random number is generated. The user is asked to enter a key. The array of random numbers are sorted and then the binary search operation is performed based on the key.

Below is the source code for C Program to implement Binary Search using Recursion which is successfully compiled and run on Windows System to produce desired output as shown below :


SOURCE CODE : :


/*  C Program to implement Binary Search using Recursion  */


#include <stdio.h>
 
void binary_search(int [], int, int, int);
void bubble_sort(int [], int);
 
int main()
{
    int key, size, i;
    int list[25];
 
    printf("Enter size of a list: ");
    scanf("%d", &size);
    printf("Generating random numbers\n");
    for(i = 0; i < size; i++)
    {
        list[i] = rand() % 100;
        printf("%d  ", list[i]);
    }
    bubble_sort(list, size);
    printf("\n\n");
    printf("Enter key to search\n");
    scanf("%d", &key);
    binary_search(list, 0, size, key);
 
}
 
void bubble_sort(int list[], int size)
{
    int temp, i, j;
    for (i = 0; i < size; i++)
    {
        for (j = i; j < size; j++)
        {
            if (list[i] > list[j])
            {
                temp = list[i];
                list[i] = list[j];
                list[j] = temp;
            }
        }
    }
}
 
void binary_search(int list[], int lo, int hi, int key)
{
    int mid;
 
    if (lo > hi)
    {
        printf("Key not found\n");
        return;
    }
    mid = (lo + hi) / 2;
    if (list[mid] == key)
    {
        printf("Key found\n");
    }
    else if (list[mid] > key)
    {
        binary_search(list, lo, mid - 1, key);
    }
    else if (list[mid] < key)
    {
        binary_search(list, mid + 1, hi, key);
    }
}}

Output : :


***************** OUTPUT ********************


***************** FIRST RUN *****************

Enter size of a list: 10
Generating random numbers
83  86  77  15  93  35  86  92  49  21  
 
Enter key to search
21
Key found



***************** SECOND RUN *****************

Enter size of a list: 7
Generating random numbers
41  67  34  0  69  24  78

Enter key to search
23
Key not found

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in the short interval.


Thanks for reading the post….

Leave a Reply