An element in a sorted array can be found in O(log n) time via binary search. But suppose I rotate the 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

Searchanelementinasortedandpivotedarray.java

/**
 * 
 * An element in a sorted array can be found in O(log n) time via
 *  binary search. But suppose I rotate the 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
 * @author paveynganpi
 *
 */


public class Searchanelementinasortedandpivotedarray {
	
	public static int findPivot(int[] arr, int low, int high){
		
		if(high <low){return -1;}
		if(low == high){return low;}
		
		int mid = (high+low)/2;
		if(mid<high && arr[mid] > arr[mid+1]){return mid;}
		else if(mid>low && arr[mid] <arr[mid-1]){return mid-1;}
		else if(arr[low] > arr[mid]){
			return findPivot(arr, low, mid-1);
			
		}
		else{
			return findPivot(arr, mid+1, high);
		}
	}
	
	public static int binarySearch(int[] arr, int low, int high, int n){
		
			if(high<low){return -1;}
			
			int mid = (high+low)/2;
			if(arr[mid] == n){return mid;}
			if(n<arr[mid]){
				return binarySearch(arr, low,( mid-1), n);
			}
			else {
				return binarySearch(arr, (mid+1), high, n);
			}
			
		
		
	}
	
	public static int pivotBinarySearch(int[] arr, int low, int high , int num){
		
		int pivot = findPivot(arr, 0, arr.length-1);
		int mid = (high+low)/2;
		if(pivot == -1){return binarySearch(arr, 0, arr.length-1, num);}
		if(arr[pivot] == num){return pivot;}
	    if(arr[0]<= num){ return binarySearch(arr, low, pivot-1, num);}
		else {
			return binarySearch(arr, pivot+1, high, num);
		}
		
		
	}
	
	public static void main(String[]args ){
		
		int[] arr = {3, 4, 5, 6, 1, 2};
		//System.out.println(findPivot(arr, 0, arr.length-1));
		System.out.println(pivotBinarySearch(arr, 0, arr.length-1, 4));
	}

}