# Binary Search using Recursion

Saurabh | Apr 10, 2010 | Comments 4

As a simple rule of recursion, any function can be computed using a recursive routine if :

1. The function can be expressed in its own form.

2. There exists a termination step, the point at which f(x) is known for a particular ‘x’.

Therefore to write a recursive program for the binary search, we have to express the binary search function in a recursive form using the above 2 rules :

where ‘n’ is the element to be searched and low and high the lower and upper bounds of the array

2. if(n == a[mid]) print mid. (termination step)

The exe file can be downloaded from here : Recursive Binary Search

Using these 2 rules, the recursive program for binary search can be coded very easily as shown :

```
#include "stdio.h"
binarysearch(int a[],int n,int low,int high)
{ int mid;
if (low > high)
return -1;
mid = (low + high)/2;
if(n == a[mid])
{ printf("The element is at position %d\n",mid+1);
return 0;
}
if(n < a[mid])
{ high = mid - 1;
binarysearch(a,n,low,high);
}
if(n > a[mid])
{ low = mid + 1;
binarysearch(a,n,low,high);
}
}
main()
{ int a[50];
int n,no,x,result;
printf("Enter the number of terms : ");
scanf("%d",&no);
printf("Enter the elements :\n");
for(x=0;x<no;x++)
scanf("%d",&a[x]);
printf("Enter the number to be searched : ");
scanf("%d",&n);
result = binarysearch(a,n,0,no-1);
if(result == -1)
printf("Element not found");
return 0;
}
```

**About the Author**: Software Engineer - Advanced Search & Recommendation at Rovi

Hey, Just what I was browsing for! I was researching articles and reviews for our online site when I came across your article on ” Binary Search using Recursion | programminggeeks.com ” which I found on AOL. We would love you to write for us, if interested. I’ve bookmarked this post for future reference. Good comments here as well –

/*I made slight corrections so that the the code can be executed directly, very well written (^_^)*/

#include

void binarysearch(int a[],int n,int low,int high)

{

int mid;

if (low > high)

return -1;

mid = (low + high)/2;

if(n == a[mid])

{

printf(“The element is at position %d\n”,mid+1);

return 0;

}

if(n a[mid])

low = mid + 1;

binarysearch(a,n,low,high);

}

void main()

{

int a[50];

int n,no,x,result;

printf(“Enter the number of terms : “);

scanf(“%d”,&no);

printf(“Enter the elements :\n”);

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

scanf("%d",&a[x]);

printf("Enter the number to be searched : ");

scanf("%d",&n);

result = binarysearch(a,n,0,no-1);

if(result == -1)

printf("Element not found");

getch();

}

int binary(int A[ ], int n, int num, int low, int upp){

int mid, search = 0;

if(low <= upp){

mid = (low + upp)/2;

if(num == A[mid]) search = 1;

else if(num < A[mid])

return binary(A, n, num, low , mid?1);

else

return binary(A, n, num, mid+1, upp);

}

else return search;

}

Nice work…Man