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

  • Article

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.