Binary Search using Recursion

  1. //Binary Search   
  2. //Time Complexity  
  3. //Best Case O(1)  
  4. //Worst Case O(logn)  
  5.   
  6. #include <stdio.h>  
  7. #include <conio.h>  
  8.   
  9. int BinarySearchUsingRecursion(int a[],int n,int search,int start,int end);  
  10. int main()  
  11. {  
  12.     printf("Binary Search\n");  
  13.     int arr[100],n,search,result=0;  
  14.     printf("Enter the number of elements in the array\n");  
  15.     scanf("%d",&n);  
  16.     printf("Enter the array elements in Ascending order");  
  17.     for(int i=0;i<n;i++)  
  18.     {  
  19.         scanf("%d",&arr[i]);  
  20.     }  
  21.     printf("The entered array elements are\n");  
  22.     for(int i=0;i<n;i++)  
  23.     {  
  24.         printf("%d\n",arr[i]);  
  25.     }  
  26.     printf("Enter the search element\n");  
  27.     scanf("%d",&search);  
  28. result= BinarySearchUsingRecursion( arr, n,search,0,n-1);  
  29. if(result==-1)  
  30. {  
  31.     printf("Element not found\n");  
  32. }  
  33. else  
  34. {  
  35.     printf("Element Found at position %d\n",result);  
  36. }  
  37.     return 0;  
  38. }  
  39. int BinarySearchUsingRecursion(int a[],int n,int search,int start,int end)  
  40. {  
  41. int mid=0;  
  42. if(start>end)  
  43. {  
  44.     return -1;  
  45. }  
  46. mid=(start+end)/2;  
  47. if(search==a[mid])  
  48. return mid+1;  
  49. else if(search<a[mid])  
  50. {  
  51.     return BinarySearchUsingRecursion( a, n,search,start,mid-1);  
  52.   
  53. }  
  54. else if(search>a[mid]){  
  55. return BinarySearchUsingRecursion( a, n,search,mid+1,end);  
  56. }  
  57. return -1;  
  58. }