Recursive Binary search

Time Complexity -O(log n)

 C Program with Function

 Imp Note : For binary search array should be sorted i.e. either ascending order or Descending Order

 #include <stdio.h>

int binary_Search(int arr[], int l, int r, int key) ;//function Prototype

  int i=0; // global declaration for counting pass for binary search

int main()

{

   

int i,n,key,arr[10],result; // declaration part

printf("\n Enter size of array:");

scanf("%d",&n);

printf("\n Enter element of array:");

for(i=0;i<n;i++)   // Scan array of size n

{

    scanf("%d",&arr[i]);

   

}

printf("\n Entered array is:");

for(i=0;i<n;i++)   // Print array

{

    printf("\"%d\"\t",arr[i]);

   

}

printf("\n Enter key to find in aray:");

scanf("%d",&key);   //scan key for finding

 result = binary_Search(arr, 0, n-1, key);

   if(result == -1)

 {

printf("\n Element is not present in array");

}

else

{

                

printf("\n Element is present at index %d", result);

}

   return 0;

}

int binary_Search(int arr[], int l, int r, int key)

{

   if (r >= l)

   {

       i++;

        int mid = l + (r - l)/2;

        printf("\n pointer lacation at %d pass",i);

  printf("\n First :%d\tlast:%d\tmid: %d\t",l,r,mid);

       

        if (arr[mid] == key)   // Condition for equating mid element with key

            return mid;

 

        // If element is smaller than mid, then 

        // it can only be present in left subarray

        if (arr[mid] > key) 

            return binary_Search(arr, l, mid-1, key);

 

        // Else the element can only be present

        // in right subarray

        return binary_Search(arr, mid+1, r, key);

   }

 

   

//element not found then

   return -1;

}

/*

Output

Enter size of array:9

Enter element of array:10 20 30 40 50 60 70 80 90

Entered array is:"10" "20" "30" "40" "50" "60" "70" "80" "90"

Enter key to find in aray:40

pointer lacation at 1 pass

First :0 last:8 mid: 4

pointer lacation at 2 pass

First :0 last:3 mid: 1

pointer lacation at 3 pass

First :2 last:3 mid: 2

pointer lacation at 4 pass

First :3 last:3 mid: 3

Element is present at index 3

*/