Binary Search using Recursion

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 :

1. if(n < a[mid])
{ high = mid – 1;
binarysearch(a,n,low,high);
}
if(n > a[mid])
{ low = mid + 1;
binarysearch(a,n,low,high);
}

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)

Programming Geeks : Binary search using recursion

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&ltno;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;
	}


Related Posts

Share

Filed Under: CCodes

Tags:

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

RSSComments (3)

Leave a Reply | Trackback URL

  1. eulogy uncle says:

    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 -

  2. /*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();
    }

  3. Mahesh vanol says:

    Nice work…Man

Leave a Reply

*

AWSOM Powered