Question

compare its run time complexity with the
non recursive binary search algorithm.

Answer 1

Answer:

We can do binary search by using two ways:

1. iterative function

2. recursive function

Now for iterative function the algorithm will be:

1.  binarySearch(arr[], left, right, data)  

 2.   if (right>= left) {  

        mid = left+ (right- left) / 2;  

  3. if (arr[mid] == data)  

           return mid;  

   4.    if (arr[mid] > data)  

           return binarySearch(arr, left, mid - 1, data);

       return binarySearch(arr, mid + 1, right, data);  

   5.  return

 

  Time Complexity :  O(1)

Now for Recursive:

1.  binarySearch(arr[], int left, int right, int data)    

2.    while (left <= right) {  

        mid = left + (right - left) / 2;

3.   if (arr[mid] == data)  

           return mid;

       if (arr[mid] < data)  

           left = mid + 1;

       else

           right = mid - 1;  

 4. return  

 Time Complexity :  O(Logn)