C Program for Binary Search and Merge Search using recursion function | C Programming

C Program for Binary Search and Merge Search using recursion function

Before starting with the program to find binary search and linear search using recursion function let us know about recursion function.

Recursion Function

Recursion is a process by which a function call itself repeatedly until some specified condition has been satisfied.

                

The process is used for repetitive computation in which action is stated in terms of previous result.

                

In order to solve a problem recursively two condition must be satisfied.

• The problem must be written in a recursive form.
• The problem statement must include a problem stopping condition.

C Program for Binary Search and using recursion function

#include <stdio.h>
int binarysearch(int a[], int low, int high, int x)
{
    int mid = (low + high) / 2;
    if (low > high)
        return -1;
    if (a[mid] == x)
        return mid;
    if (a[mid] < x)
        return binarysearch(a, mid + 1, high, x);
    else
        return binarysearch(a, low, mid - 1, x);
}
int main(void)
{
    int a[100];
    int len, pos, search_item;
    printf("Enter the length of the array\n");
    scanf("%d", &len);
    printf("Enter the array elements\n");
    for (int i = 0; i < len; i++)
        scanf("%d", &a[i]);
    printf("Enter the element to search\n");
    scanf("%d", &search_item);
    pos = binarysearch(a, 0, len - 1, search_item);
    if (pos < 0)
        printf("Cannot find the element %d in the array.\n", search_item);
    else
        printf("The position of %d in the array is %d.\n", search_item, pos + 1);
    return 0;
}
C Program for Merge Search using recursion function
#include <iostream>
 
using namespace std;
// A function to merge the two half into a sorted data.
void Merge(int *a, int low, int high, int mid)
{
    // We have low to mid and mid+1 to high already sorted.
    int i, j, k, temp[high - low + 1];
    i = low;
    k = 0;
    j = mid + 1;
    // Merge the two parts into temp[].
    while (i <= mid && j <= high)
    {
        if (a[i] < a[j])
        {
            temp[k] = a[i];
            k++;
            i++;
        }
        else
        {
            temp[k] = a[j];
            k++;
            j++;
        }
    }
    // Insert all the remaining values from i to mid into temp[].
    while (i <= mid)
    {
        temp[k] = a[i];
        k++;
        i++;
    }
    // Insert all the remaining values from j to high into temp[].
    while (j <= high)
    {
        temp[k] = a[j];
        k++;
        j++;
    }
    // Assign sorted data stored in temp[] to a[].
    for (i = low; i <= high; i++)
    {
        a[i] = temp[i - low];
    }
}
// A function to split array into two parts.
void MergeSort(int *a, int low, int high)
{
    int mid;
    if (low < high)
    {
        mid = (low + high) / 2;
        // Split the data into two half.
        MergeSort(a, low, mid);
        MergeSort(a, mid + 1, high);
        // Merge them to get sorted output.
        Merge(a, low, high, mid);
    }
}
int main()
{
    int n, i;
    cout << "\nEnter the number of data element to be sorted: ";
    cin >> n;
    int arr[n];
    for (i = 0; i < n; i++)
    {
        cout << "Enter element " << i + 1 << ": ";
        cin >> arr[i];
    }
    MergeSort(arr, 0, n - 1);
    // Printing the sorted data.
    cout << "\nSorted Data ";
    for (i = 0; i < n; i++)
        cout << "->" << arr[i];
    return 0;
}

Program Explanation

1. Take input of data.
2. Call MergeSort() function.
3. Recursively split the array into two equal parts.
4. Split them until we get at most one element in both half.
5. Combine the result by invoking Merge().
6. It combines the individually sorted data from low to mid and mid+1 to high.
7. Return to main and display the result.
8. Exit.