Search an element in the sorted rotated array

Question: Implement a search function for a sorted rotated array. Duplicates are allowed. Returning any one of the duplicates is acceptable.

So for example we have sorted array as  -

2,3,6,12, 15, 18.

Now suppose the array is rotated k times ( we don't know k), such that array becomes

15, 18,2,3,6,12

Answer: We can do a binary search with some modified checks.

So lets take arr as array, start be start of the array, end be arr.length-1 and x be the number to find.

Pseudocode: 

1. Find the middle of array
2. Select the sorted array part
   If a [middle]  >  a[start] - That means this part of array is sorted and is without rotation. So, we choose array to search as [start] to a[middle] otherwise we choose a[middle] to a[end].
3. Now, depending on the array we searched in step 2, we will get the sorted array now. Now if key x lies in range of the array, we will search for the element in that range, otherwise other range. 

So, second step helps us get the sorted array on which we can apply binary search. 

Program in java

public int rotatedSearch(int[] arr, int start, int end,
                          int x){
    if(arr[start] == x){
        return start;
    } else if(arr[end] == x){
        return end;
    } else if(end - start == 1) {
        return -1;
    }

    int middle = (start + end) / 2;

//we have no rotation between start and middle, i.e. normal sorted array
//if left sub array is sorted
   if(arr[start] <= arr[middle]){
//if x is less than middle - then x may lie in this part of array
        if(x <= arr[middle] && x >= arr[start]){
            return rotatedSearch(arr, start, middle-1, x);
        } else {
            return rotatedSearch(arr, middle+1, end, x);
        }
    }
//if right sub array is sorted
    else if(arr[middle] <= arr[end]){
        if(x >= arr[middle] && x <= arr[end] ){
            return rotatedSearch(arr, middle+1, end, x);
        } else {
            return rotatedSearch(arr, start, middle-1, x);
        }
    } else {
        return -1;
    }
}

Time Complexity - O(log n)
Thanks.