CareerCup

I believe a two pass binary search would work, the first pass to find the starting of the array and the second pass to do the actual search by shifting the start, mid and end values with respect to the newly found start index.

First pass :
while(start<end)
{
mid=start+(end-start)/2;
if(a[mid]<a[start])
end=mid;
else
start=mid
}
This code will give you the index of the last element of the original array. Let this value be stored in variable 'correct'.

Second Pass:
Follow binary search algo and at each iteration correct the start, end and mid values to start+correct,mid+correct and end+correct. If these values exceed length of array then subtract the value from length.

No need for two binary searches
You already know the end of the array i.e A[k-1] (0- based index)
SO check if X<A[0]
if yes then do binary search for no on array from A[k] to A[n]
else do binary search on array from a[0] to A[k-1]
if X=A[0] return obviously
worst case would be o(logn) if k==n

The below code is for finding min_element. The same logic applies for searching too, compare mid with element to b found and check which intervals to search for.

int Solve() {
int i,j;
int n;
GI(n);
int A[n];
REP(i,n) GI(A[i]);
int ret = Find_Min(A,0,n-1);
sort(A,A+n);
cout<<ret<<"\t"<<A[0]<<endl;
if(ret==A[0]) cout<<"you are a stud :)\n";
else cout<<"you are terrible :(\n";

return 0;
}

int Find_Min(int A[],int start,int end) {
if(start<=end) {
if(start==end) return A[start];
int mid = (start+end)/2;
if(A[mid]>A[end]) return Find_Min(A,mid+1,end);
if(A[mid]<A[start]) return Find_Min(A,start,end-1);
if(A[mid]==A[start]) return A[mid];
}
}

Only one pass of binary search without knowing k

public static int binarySearch(int[] arr, int value){
	int low =0;
	int high = arr.length-1;
	while(low <= high){
		int mid = (low + high)/2;
		
		if(arr[mid] == value){ 
			return mid;
		}else if(arr[mid] > value){
			if(arr[high] > arr[mid] || arr[high] < value){
				high = mid -1;
			}else{
				low = mid + 1;
			}
		}else{
			
			if(arr[low] <= arr[mid] || arr[low] > value){
				low = mid + 1;
			}else{
				high = mid - 1;
			}
		}
	}
	return -1;
}

grt work dude.......

Here is the solution:
interviewcodesnippets.com/?p=196

boyjemmy's solution and the solution provided at interviewcodesnippets.com/?p=196 are nice, but they both have problems handling following case
3 3 3 3 3 1 2 3 (try to find 1)

i dint get, how boyjemmy solutions is taking care of "k". it's a simple binarySearch which is assuming that input array is sorted.

wwwd dot testskillshome dot com/?p=2324

What about just changing "comparator" in a standard algo so that 5 > 100, and 5 < 99:
100,5,7,99

Ha-Ha ;)

www geeksforgeeks dot org / search-an-element-in-a-sorted-and-pivoted-array/