Question

1. Please write a Divide-and-Conquer Java algorithm solving the following problem:

Given an "almost sorted" array of distinct integers, and an integer x, return the index of x in the array. If the element x is not present in the array, return -1.

"Almost sorted" means the following. Assume you had a sorted array A[0…N], and then split it into two pieces A[0…M] and A[M+1…N], and move the second piece upfront to get the following:

A[M+1]…A[N]A[0]…A[M].

Thus, the "almost sorted" array is either a sorted array, or it consists of two sorted subarrays, such that every element of the first subarray is greater or equal than every element of the second subarray.

For example, the array {3, 17, 28, 935, 1011, -10, 0, 2} is "almost sorted" since it consists of two sorted subarrays: {3, 17, 28, 935, 1011} and {-10, 0, 2} with the property that each element in the first subarray is greater or equal than every element of the second subarray.

Note: One of the subarrays can be empty, i.e., the array might be sorted.

You need to develop an efficient modification of the Binary Search Algorithm, with worst-case running time of ( ) for an array of n elements.

Reminder: In Java, elements of an array of n elements have indexes 0…n-1.

Formally speaking, your input is an array of distinct integers, and the element x to find; your output is: the index of x in the array, or -1 in case x is not there.

With the array above and x=935, the algorithm has to return 3 (the index of the element 935 in the array).

Please develop the following Java function:

public static int FindIndex(int[] arr, int x)

Here arr is the array of distinct integers, x is the element to find.

NOTE: In your algorithm, you do not have to check that the array is "almost sorted". However, you have to check "boundary cases" like an empty array.

Answer 1

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);
   }
}

output:

index of 935:3                                                                                                                                                                   

index of -10:5                                                                                                                                                                   

index of 0:6                                                                                                                                                                     

index of 1:-1                                                                                                                                                                    

index of 3:0                                                                                                                                                                     

index of 2:7                                                                                                                                                                     

index of 17:1                                                                                                                                                                    

      

//PLS give a thumbs up if you find this helpful, it helps me alot, thanks.

//if you have any doubts, ask me in the comments