PSYCHOCODES

PsychoCodes.in

Binary Search Program in C using Recursion

Binary Search is a type of searching algorithm which works on a sorted array. It finds the target value(T) by comparing the target value(T) with the middle element of the array. If the target value(T) is greater or smaller than the middle element of the array then the array gets divided into two parts on the basis of the middle element.

Also Read : Size of an array using Recursion in C

Binary Search Algorithm is as follows

1- Set start to 0 and end to n-1 where n is the size of the array.
2- if start > end search ends as unsuccessful.
3- set mid = floor((start+end)/2).
4- If array[m] > T, set end = m-1 and go to step 2.
5- If array[m] < T, set start = m+1 and go to step 2.
6- If array[m] = T, return m.

Let’s see a simple example on Binary Search Algorithm.

arr[] = {10, 34, 56, 78, 90, 178}

Note: Remeber the array must be in sorted form.

Binary Search Example in C

Now let’s see the program for above algorithm in C and C++ language, first we will create function called binarySearch() having following parameters.

int binarySearch(int x[],int element,int start,int end)

x[ ] – array in which the element is to be searched.

element – the value to be searched.

start – starting index of the array.

End – ending index of the array.

Now let’s write the function body.

int binarySearch(int x[],int element,int start,int end){
	int mid,noOfElements,i;	
	mid = (int)(start+end)/2;
	printf("%d",mid);
	if(x[mid] == element)
		return mid;
	else if(start==end)
		return -1;
	else if(x[mid] < element){
		start = mid+1;
		binarySearch(x,element,start,end);
	}
	else{
		start = 0;
		end = mid-1;
		binarySearch(x,element,start,end);	}}

Now let’s see the driver function and use our binarySearch() function in it.

int main(){
	int x[20],n,i,index,start=0,end,element;
	printf("Enter number of  elements: ");
	scanf("%d",&n);
	end = n;
	printf("Enter array elements: ");
	for(i=0;i<n;i++){
		scanf("%d",&x[i]);
	}
	printf("Enter the element to search: ");
	scanf("%d",&element);
	index = binarySearch(x,element,start,end-1);
	if(index == -1)
		printf("Element Not Found.\n");
	else
		printf("Element found at index : %d\n",index);
	

	return 0;
}

Complete Program for Binary Search in C

#include<stdio.h>

int binarySearch(int x[],int element,int start,int end);
int main(){
	int x[20],n,i,index,start=0,end,element;
	printf("Enter number of  elements: ");
	scanf("%d",&n);
	end = n;
	printf("Enter array elements: ");
	for(i=0;i<n;i++){
		scanf("%d",&x[i]);
	}
	printf("Enter the element to search: ");
	scanf("%d",&element);
	index = binarySearch(x,element,start,end-1);
	if(index == -1)
		printf("Element Not Found.\n");
	else
		printf("Element found at index : %d\n",index);
	

	return 0;
}

int binarySearch(int x[],int element,int start,int end){
	int mid,noOfElements,i;	
	mid = (int)(start+end)/2;
	if(start > end)
		return -1;
	if(x[mid] == element)
		return mid;
	else if(x[mid] < element){
		start = mid+1;
		binarySearch(x,element,start,end);
	}
	else{
		start = 0;
		end = mid-1;
		binarySearch(x,element,start,end);	
	}
			
}

Thank you for reading.

Tweet your queries and feedback to @PsychoCodes or leave a message on our Facebook page. You can also comment your questions below.

Also, don't forget to subscribe to our Newsletter. If you like this article, then please share it and help us grow.

If You Love this article, You Should Consider:

  • Like us on Facebook
  • Follow us on Instagram
  • Follow us on Twitter
  • Subscribe to our Newsletter.
  • Let us know your suggestions and queries in the comments below.

Thank you for your Love and Support

Share your thoughts