CareerCup

what does shifted 'downward' or 'upward' mean? Is it shift left and right??

Find the pivot element, i.e the initial random number using binary search and perform the binary search on left or right part.

I think the problem is :
Suppose we have an array {1 2 3 4 5 6 7}. We choose a random number lets say 3. Now all elements on right of 3 are moved to its left and vice versa.The array then is {4 5 6 7 3 1 2}. We need to search for a particular number in this array.
I hope its correct.

decide whether the sequence is asending or descending. now find the pivot by
dividing the data set into 2 power parts(we have 1, 3, 7 ... partition points and compare the data at those points, as you know whether they are ascending or descending) and find where the flow of ascending or descending breaks (and starts again).. and there we have pivot. after finding pivot, it is cakewalk with binary search.. read till you understand..

Ok, nagendra can you please give the basic idea or a proof of concept behind your approach. I can see that it works but cant convince myself.

And yes can somebody or the one who posted the ques throw light on the fact "whether we know the position of the pivot while shuffling the array". If yes the ques is pretty straight forward.

Suppose the elements are {10,15,20,25,30,35,40} and the random no is 20. The new array would be {25,30,35,40,20,10,15}. Suppose the no. to be searched is x.
Step1. Find index of random no. i.e 20. can be done in O(n) or could have been cached earlier.
Step2. Check x with random no i.e Array[index] i.e 20.
Step3. If x is greater than random no, then do binary search between elements 0 to index-1. If x is less than random no, then do binary search between elements index+1 to Arraymax
Every one knows binary search.
The logic is that all elements above random no is sorted and all elements below random no are sorted. Hence we need to manually identify where x falls and then use binary search

Hi Avinash. If pivot element is the first number or second number, you end up scanning the whole array. So it is O(n).
If you are using an O(n) solution then why search for pivot element, you could have searched for the key itself. So this is not a good solution.

binSearch(int low,int high,int data, int arr[]){
   mid = (high + low) /2;
   if (A[mid-1] < A[mid] && A[mid] < A[mid-1]){ // we are in the increasing range
     if(A[mid) < data)
       binSearch(mid,high,data,arr)
     else
       binSearch(low,mid,data,arr)
   }
   else{ // we are decreasing range
     if(A[mid] < data)
        binSearch(low,mid,data,arr)
     else
        binSearch(mid,high,data,arr)
   }   
}

@anonymous:check your if condition,I suppose u meant A[mid-1]<A[mid]&&A[mid]<A[mid+1].Now,If my array is {0,1,2,3,4,5,6,7,8,9} and pivot is 7 then new array would become {8,9,7,0,1,2,3,4,5,6}.If I am searching for 9 then according to your code after,checking conditions of middle your code would start a binary search on subarray {1 2 3 4 5 6}..Thus giving wrong answer

Find the pivot point, divide the array in two sub-arrays and call binary search.
The main idea for finding pivot is – for a sorted (in increasing order) and pivoted array, pivot element is the only only element for which next element to it is smaller than it.
Using above criteria and binary search methodology we can get pivot element in O(logn) time

Input arr[] = {3, 4, 5, 1, 2}
Element to Search = 1
1) Find out pivot point and divide the array in two
sub-arrays. (pivot = 2) /*Index of 5*/
2) Now call binary search for one of the two sub-arrays.
(a) If element is greater than 0th element then
search in left array
(b) Else Search in right array
(1 will go in else as 1 < 0th element(3))
3) If element is found in selected sub-array then return index
Else return -1.

Find pivot which can be done in o(logn) as follows
a= arr[0], b=arr[last].....now b < pivot < a ...pre check if pivot is a or b
1 left=0, right=end, mid=(left+right)/2
2 if(arr[mid] < arr[mid-1]) then pivot is at mid
else if(arr[mid] <a) then mid =(left+mid)/2 and right = old value of mid
else mid=(right+mid)/2 and left = old value of mid
loop until pivot is found

3. now that pivot postion is fond ..search the element on required side of arrray using binary search...
this gives algo in o(logn)

bool binsearch(int *arr, int l, int h, int searchElement)
{
int mid = (h-l)/2;

if(l>= h)
return false;
if(arr[mid] == searchElement)
return true;
else if(searchElement > arr[mid])
binsearch(arr, mid+1,h,searchElement);
else
binsearch(arr,l,mid-1,searchElement);
}

bool FindElement(int *arr, int circShifted, int SearchElement,int length)
{
if(arr[circShifted] == SearchElement)
return true;
else
return (binsearch(arr,0,circShifted-1,SearchElement) || binsearch(arr,circShifted+1,length,SearchElement));
}