In my previous article C Program for Binary Search I explained how to use binary search algorithm to search an element in a sorted array. In that article you learnt how to implement binary search algorithm using C programing language. Today I'm going to show you how to implement binary search algorithm in C using recursion. Recursion is programming technique where a function calls itself to solve a smaller problem that is of the same type as the original problem. The recursive call (calling itself) continues until the function can produce a result trivially without making any more calls.
In the program below, the function binarysearch takes four parameters - the array to be searched, the lowest position of the search range, highest position of the search range, and the element to be searched.
The first time you call the binary search function with the entire range of the arra. So you set the lowest position to 0 and highest position to the length of the array minus one.
With each recursive call the search range becomes smaller and smaller until you find the search element.
#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;
}
Consider an array of 10 elements as below.
Consider for example you want to search for 85 which is the sixth element (index position 5) in the array. In this case, the recursive calls to the binary search function will be performed as shown in the figure below.
As you can see the above diagram, the search range becomes smaller and smaller with each recursive call of binarysearch function. The first call to binarysearch function tries to find the search element in array position 0 to 9. In the second call you chop the array in two slices and perform the search on elements from 5 to 9. Search range on the third call is from position 5 to 6.
