C Programming Code Examples

C > Sorting Searching Code Examples

C Program to Perform Binary Search using Recursion



C Program to Perform Binary Search using Recursion

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.

    #include <stdio.h>

    void binary_search(int [], int, int, int);

    void bubble_sort(int [], int);

    int main()

    {

        int key, size, x;

        int list[25];

        printf("Enter size of a list: ");

        scanf("%d", &size);

        printf("Generating random numbers\n");

        for(x = 0; x < size; x++)

        {

            list[x] = rand() % 100;

            printf("%d  ", list[x]);

        }

        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, x, j;

        for (x = 0; x < size; x++)

        {

            for (j = x; j < size; j++)

            {

                if (list[x] > list[j])

                {

                    temp = list[x];

                    list[x] = 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);

        }

    }
}