Divide and conquer algorithm in java

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.