C Program to Perform Binary Search using Recursion

This C program demonstrates the binary search algorithm using recursion. Binary search is an efficient algorithm for finding a specific element in a sorted array.

Binary search is an efficient algorithm used to search for a specific element in a sorted array or list. It works by repeatedly dividing the search space in half and comparing the middle element with the target value. This process is performed recursively until the target value is found or the search space is exhausted. The key advantage of binary search is its efficiency. It has a time complexity of O(log n), where n is the number of elements in the array.

Problem Statement

Problem: Given a sorted array of integers and a target value, write a C program to find the index of the target value in the array using binary search. If the target value is not found, return -1.

Input:

• An array of integers in ascending order.
• The size of the array.
• The target value to search for.

Output:

• The index of the target value in the array if found, or -1 if not found.

If the target value is not present in the array, the program should output “Element not found in the array.” For example:

Input: Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] Size: 10 Target: 30

Output: Element not found in the array.

The program should return -1 to indicate that the target value 30 is not present in the array.

C Program to Perform Binary Search using Recursion

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int key) {
    if (low <= high) {
        int mid = low + (high - low) / 2;

        // If the key is present at the middle
        if (arr[mid] == key)
            return mid;

        // If the key is smaller than the middle element
        if (arr[mid] > key)
            return binarySearch(arr, low, mid - 1, key);

        // If the key is larger than the middle element
        return binarySearch(arr, mid + 1, high, key);
    }

    // Key not found
    return -1;
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 23;
    int result = binarySearch(arr, 0, n - 1, key);

    if (result == -1)
        printf("Element not found in the array.\n");
    else
        printf("Element found at index %d.\n", result);

    return 0;
}

How it Works

1. The binary search algorithm starts by defining the search space, which is the entire array. It sets the lower bound (low) to the first index of the array and the upper bound (high) to the last index of the array.
2. The algorithm calculates the middle index as mid = low + (high - low) / 2. This finds the index of the middle element in the current search space.
3. It compares the middle element (arr[mid]) with the target value. There are three possible cases:
   • If arr[mid] is equal to the target value, the search is successful, and the algorithm returns mid as the index of the target value in the array.
   • If arr[mid] is greater than the target value, it means the target value can only be present in the lower half of the current search space. The algorithm updates high = mid - 1 to narrow down the search space to the lower half and repeats the process from step 2.
   • If arr[mid] is smaller than the target value, it means the target value can only be present in the upper half of the current search space. The algorithm updates low = mid + 1 to narrow down the search space to the upper half and repeats the process from step 2.
4. The algorithm continues dividing the search space in half and repeating steps 2 and 3 until either the target value is found or the search space is exhausted (i.e., low > high). If the search space is exhausted, it means the target value is not present in the array, and the algorithm returns -1 to indicate that.

By dividing the search space in half with each iteration, binary search efficiently narrows down the possible locations of the target value. This results in a significant reduction in the search space with each step, leading to a time complexity of O(log n), where n is the number of elements in the array. This makes binary search highly efficient, especially for large sorted arrays.

Input /Output

Input: Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

Size: 10

Target: 23

Output:

Element found at index 5.

Explanation:

In this example, the input array is [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], and its size is 10. We want to search for the target value 23. The program uses binary search to find the index of the target value in the array. Since 23 is present at index 5 in the array, the output is “Element found at index 5.”