Question

For the problem below, please estimate the worst-case Running Time for a random array of size n, and prove that it is indeed ( ). Please show all your work. Just stating something like "since 2 Binary Search runs in ( ) time, our algorithm has the same runtime estimate" is not enough. A rigorous explanation is expected.

import java.util.*;
public class Main
{
static int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
  
// If the element is present at the middle itself
if (arr[mid] == x)
return mid;
  
// If element is smaller than mid, then it can only
// be present in left subarray
if (arr[mid] > x)
{ int rr= binarySearch(arr, l, mid - 1, x);
if(rr==-1)//modified
{
return binarySearch(arr, mid + 1, r, x);
}
return rr;
}
// Else the element can only be present in right
// subarray
int k =binarySearch(arr, mid + 1, r, x);
//modified part
if(k==-1)
{
return binarySearch(arr, l, mid - 1, x);
}
return k;
}
  
// We reach here when element is not present in array
return -1;
}
  
public static int FindIndex(int[] arr, int x)
{
if(arr.length==0)return -1;//if array is empty
return binarySearch(arr,0,arr.length-1,x);
  
}
   public static void main(String[] args) {
   int a[] = {3, 17, 28, 935, 1011, -10, 0, 2} ;//declaring array
   int r = FindIndex(a,935);
       System.out.println("index of 935:"+r);
       r = FindIndex(a,-10);
       System.out.println("index of -10:"+r);
      
       r = FindIndex(a,0);
       System.out.println("index of 0:"+r);
      
       r = FindIndex(a,1);
       System.out.println("index of 1:"+r);
      
       r = FindIndex(a,3);
       System.out.println("index of 3:"+r);
      
       r = FindIndex(a,2);
       System.out.println("index of 2:"+r);
      
       r = FindIndex(a,17);
       System.out.println("index of 17:"+r);
   }
}

Answer 1

Please find the STEP-BY-STEP SOLUTION Below.