Searching For a Number in Shifted Sorted Array within O(log(n)) time


Run into the algorithm problem long time ago. Now post my answer here. A sorted array, say: {1,2,3,4,5,6,7,8,9,10,11,12}, do right rotate through carry unknown times, and then it might become: {6,7,8,9,10,11,12,1,2,3,4,5}. Now we need get the index of a given number, say 4, from the array within O(log(n)) time. Apparently a 8-year-old can get it done with O(n) time.


We can think of it this way: take the middle element of array, if target is found, fine; if not, and then array become two parts, one is sorted array, the other is shifted sorted array. As illustrated as below diagram:



If the target falls into the sorted array half, we can simple do a binary search; otherwise, repeat this operation in the other half in recursive way. You can see this is divide-and-conquer algorithm. Obviously this is O(log(n)).


Code






//


// A typical binary search implementation


//


int _BinarySearch(unsigned int ShiftedArray[], unsigned int start, unsigned int end, unsigned int target)


{


    // Not found


    if( start == end && ShiftedArray[start] != target) {


       return -1;


    }


 


    unsigned int middle = start + (end - start)/2;


    if(target == ShiftedArray[middle])


    {


       return middle;


    } else if (target > ShiftedArray[middle]) {


       return _BinarySearch(ShiftedArray, middle + 1, end, target);


    } else {


       return _BinarySearch(ShiftedArray, start, middle - 1, target);


    }


}


 


//


// Select a given number from shifted array.


// ShiftedArray is something like = {6,7,8,9,10,11,12,1,2,3,4,5}


// If found, return index of the number; if not, reutrn -1


// Require log(N)


//


int SearchShiftedArray(unsigned int ShiftedArray[], unsigned int start, unsigned int end, unsigned int target)


{


    // Start meets end


    if( start == end && ShiftedArray[start] != target) {


       return -1;


    }


 


    unsigned int middle = start + (end - start)/2;


    if(target == ShiftedArray[middle])


    {


       return middle;


    } else if(ShiftedArray[middle] < ShiftedArray[start]) { // Right half is sorted linearly


       if((target > ShiftedArray[middle]) && (target <= ShiftedArray[end])) {


           return _BinarySearch(ShiftedArray, middle + 1, end, target);


       } else {


           return SearchShiftedArray(ShiftedArray, start, middle-1, target);


       }


    } else { // Left half is sorted linearly


       if((target >= ShiftedArray[start]) && (target < ShiftedArray[middle])) {


           return _BinarySearch(ShiftedArray, start, middle - 1, target);


       } else {


           return SearchShiftedArray(ShiftedArray, middle + 1, end, target);


       }


    }


}


 


Test cases






Positive: {6,7,8,9,10,11,12,1,2,3,4,5}, target = 3, target = 8


Negative: {6,7,8,9,10,11,12,1,2,3,4,5}, target = 0, target = 13


Boundary: {6,7,8,9,10,11,12,1,2,3,4,5}, target = 6, target = 5


Exceptional: {…max}, target = max


 One more interesting thing is the statement that “only about 10 percent of the professional programmers implemented binary search correctly.” Do you know why? Check this.

Skip to main content