Search an element in a sorted and rotated array

An element in a sorted array can be found in O(log n) time via binary search. But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time.



Code:

package microsoftInterviewPrep;

public class SearchSortedRotatedArray {

    static void pivotedBinarySearch(int[] a, int key){

        int n = a.length -1;
        int pivot = findPivot(a, 0, n);


        if(a[pivot] == key)
            System.out.println(pivot);

        else if(key > a[0])
            System.out.println(binarySearch(a, 0, pivot-1, key));
        else
            System.out.println(binarySearch(a, pivot+1, n, key));

    }
  

    static int findPivot(int[] a, int low, int high){

        if(high < low)
            return -1;

        int mid = (low + high) / 2;

        if( a[mid] > a[mid+1])
            return mid;

        if(a[low] > a[mid])
            return findPivot(a, low, mid-1);
      
        return findPivot(a, mid+1, high);  

    }

    static int binarySearch(int[] a, int low, int high, int key){

        if(high < low){
            return -1;
        }

        int mid = (low+high)/ 2;

        if(key == a[mid])
            return mid;
      
        if(key < a[mid])
            return binarySearch(a, low, mid-1, key);

        return binarySearch(a, mid+1, high, key);
    }

    public static void main(String[] args){

        int a[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};

        int key = 3;
      
        pivotedBinarySearch(a, key);
    }

}



Output:

8