# 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. 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,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."); else printf("Element found at index : \%d",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,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."); else printf("Element found at index : \%d",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); }  }``

Preorder and Postorder Traversal of binary tree in Python
02 September 2018

Binary Tree in Python
02 September 2018

Explaining Register variables in C with examples
17 August 2018

Data Autosave System using PHP, MySQL and AJAX
06 July 2018

Понравилась статья? Поделиться с друзьями: