**When some elements at the beginning of an array are moved to the end, it gets a rotation of the original array. Please implement a function to search a number in a rotation of an increasingly sorted array. Assume there are no duplicated numbers in the array.**

__Question:__
For example, array {3, 4, 5, 1, 2} is a rotation of array {1,
2, 3, 4, 5}. If the target number to be searched is 4, the index of the number
4 in the rotation 1 should be returned. If the target number to be searched is
6, -1 should be returned because the number does not exist in the rotated
array.

**Binary search is suitable for sorted arrays. Let us try to utilize it on a rotation of a sorted array. Notice that a rotation of a sorted array can be partitioned into two sorted sub-arrays, and numbers in the first sub-array are greater than numbers in the second one.**

__Analysis:__
Two pointers P1 and P2 are utilized. P1 references to the first
element in the array, and P2 references to the last element. According to the
rotation rule, the first element should be greater than the last one.

The algorithm always compares the number in middle with numbers
pointed by P1 and P2 during binary search. If the middle number is in the first
increasingly sorted sub-array, it is greater than the number pointed by P1.

If the value of target number to be search is between the
number pointed by P1 and the middle number, we then search the target number in
the first half sub-array. In such a case the first half sub-array is in the
first increasing sub-array, we could utilize the binary search algorithm. For
example, if we search the number 4 in a rotation {3, 4, 5, 1, 2}, we could
search the target number 4 in the sub-array {3, 4, 5} because 4 is between the
first number 3 and the middle number 5.

If the value of target number is not between the number
pointed by P1 and the middle number, we search the target in the second half
sub-array. Notice that the second half sub-array also contains two increasing
sub-array and itself is also a rotation, so we could search recursively with
the same strategy. For example, if we search the number 1 in a rotation {3, 4,
5, 1, 2}, we could search the target number 1 in the sub-array {5, 1, 2} recursively.

The analysis above is for two cases when the middle number
is in the first increasing sub-array. Please analyze the other two cases when
the middle number is in the second increasing sub-array yourself, when the
middle number is less than the number pointed by P2.

The code implementing this algorithm is listed below, in C/C++:

int
searchInRotation(int numbers[], int length, int k)

{

if(numbers == NULL || length <= 0)

return
-1;

return
searchInRotation(numbers, k, 0, length - 1);

}

int
searchInRotation(int numbers[], int k, int start, int end)

{

if(start
> end)

return
-1;

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

if(numbers[middle]
== k)

return
middle;

// the middle
number is in the first increasing sub-array

if(numbers[middle]
>= numbers[start])

{

if(k
>= numbers[start] && k < numbers[middle])

return
binarySearch(numbers, k, start, middle - 1);

return
searchInRotation(numbers, k, middle + 1, end);

}

// the middle
number is in the second increasing sub-array

else if(numbers[middle] <= numbers[end])

{

if(k
> numbers[middle] && k <= numbers[end])

return
binarySearch(numbers, k, middle + 1, end);

return
searchInRotation(numbers, k, start, middle - 1);

}

// It should
never reach here if the input is valid

assert(false);

}

Since the function binarySearch is for the classic binary
search algorithm, it is not listed here. You might implement your own binary
search code if you are interested.

In each round of search, half of the array is excluded for
the next round, so the time complexity is O(log

*n*).
You may wonder why we assume there are no duplications in the
input array. We determine whether the middle number is in the first or second sub-array
by comparing the middle number and the numbers pointed by P1 or P2. When the
middle number, the number pointed by P1 and P2 are identical, we don’t know
whether the middle number is in the first or second increasing sub-array.

Let’s look at some examples. Two arrays {1, 0, 1, 1, 1} and {1,
1, 1, 0, 1} are both rotations of an increasingly sorted array {0, 1, 1, 1, 1},
which are visualized in Figure 1.

**Figure 1: Two rotations of an increasingly sorted array {0, 1, 1, 1, 1}: {1, 0, 1, 1, 1} and {1, 1, 1, 0, 1}. Elements with gray background are in the second increasing sub-array.**

In Figure 1, the elements pointed by P1 and P2, as well as
the middle element are all 1. The middle element with index 2 is in the second
sub-array in Figure 1 (a), while the middle element is in the first sub-array
in Figure 1 (b).

Since we can’t determine whether the middle
number in the first or second increasing sub-array, we have to search
sequentially for such cases, and our code listed above should be revised.
More coding interview questions are discussed in my
book <Coding Interviews: Questions, Analysis & Solutions>. You may
find the details of this book on Amazon.com, or
Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

This doesn't work when k = 14 for this input array {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14};

ReplyDeleteit works, I have tested, the solution is correct

DeleteBTW, i used my version of binary search

ReplyDeletestatic int binarySearch(int[] a, int object, int left, int right) {

int l = left;

int r = right;

while (l <= r) {

int mid = l + (r - l)/2;

if (a[mid] == object) return mid;

else if (object < a[mid]) {

r = mid - 1;

} else {

l = mid + 1;

}

}

return -1;

}

Hello there! Thanks for providing such an awesome resource with your site here. I was hoping you might be interested in swapping links.

ReplyDeleteI’m working on a little site that specializes in providing job interview tips. It’s a humble operation and we’re trying to build our exposure up now.

Keep up the great work! Your site looks fantastic Cheers!

Useful algo. Thank you.

ReplyDeleteHave a look at my solution. Please give feedback. htpp://knavite.blogspot.com/2013/11/searching-element-in-rotated-sorted.html

ReplyDeleteCheck this for c# interview questions @ http://skillgun.com

ReplyDeletefunction find(list, n)

ReplyDelete{

var start = 0;

for(var i = 0; i + 1 < list.length; i++)

{

if (list[i] > list[i + 1])

{

start = i + 1;

break;

}

}

for(var a = 0, b = list.length; a < b;)

{

var r = Math.floor((b - a) / 2);

var j = (a + r + start) % list.length;

console.log("j=" + j + " list[j]=" + list[j]);

if (list[j] == n) return true;

if (list[j] > n) b = a + r;

else a += r + 1;

if (r == 0) break;

}

return false;

}