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.
