Binary Search in C using Recursion. Binary search is a highly efficient algorithm to find the position of a target element within a sorted array. By dividing the search interval in half, binary search minimizes the number of comparisons needed to locate the target element, making it significantly faster than the target element, especially for large data sets. Implementing binary search using recursion in C programming can be an interesting exercise to understand both the algorithm and concept of the recursion. In this article, we will go through the process of implementing a recursive binary search in C.
Implementing Recursive Binary Search in C
Here is a step-by-step guide to implementing a recursive binary search in C.
Function Signature
The function will take four parameters- The array, the target element, the start index, and the end index of the array. The function will return the index of the target element in the array.
int binarySearch(int arr[], int target, int start, int end);Base Case
If the start index is greater than the end index, it means the target element is not present in the array in this case return-1.
if (start > end) return -1;Finding the Middle Element
Calculate the middle index to compare with the target element. To prevent overflow, use start+(end-start)/2 instead of (start + end)/2.
int mid = start + (end - start) / 2;Comparison and Recursion
If the target element matches the middle element, return the middle index. If the target element is less than the middle element, recursively search these left sub-arrays. Otherwise, search the right subarray.
if (arr[mid] == target) return mid;
else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
else return binarySearch(arr, target, mid + 1, end);Complete Recursive Binary Search Function in C
After combining the above steps, the complete recursive binary search function looks like this-
int binarySearch(int arr[], int target, int start, int end) {
if (start > end) return -1;
int mid = start + (end - start) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
else return binarySearch(arr, target, mid + 1, end);
}Binary Search in C using Recursion
Let’s write the complete C program that uses recursive binary search-
#include<stdio.h>
int binarySearch(int arr[], int target, int start, int end) {
if (start > end) return -1;
int mid = start + (end - start) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
else return binarySearch(arr, target, mid + 1, end);
}
void main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 10;
int result = binarySearch(arr, target, 0, n - 1);
if (result == -1) printf("Element is not present in array");
else printf("Element is present at index %d", result);
}Output
Implementing binary search using recursion in C not only helps in understanding the binary search algorithm but also offers a practical insight into how recursion works in C programming. This approach is efficient and elegant for searching operations in sorted arrays, Showcasing the power of combining recursion with the divide-and-conquer strategy.
Happy Coding & Learning