Searching a number in a rotated sorted Array

Question

Given a Sorted Array which can be rotated find an Element in it in minimum Time Complexity.

eg : Array contents can be [8, 1, 2, 3, 4, 5]. Assume you search 8 in it.

Answer 1

The solution still works out to a binary search in the sense that you'll need to partition the array into two parts to be examined.

In a sorted array, you just look at each part and determine whether the element lives in the first part (let's call this A) or the second part (B). Since, by the definition of a sorted array, partitions A and B will be sorted, this requires no more than some simple comparisons of the partition bounds and your search key.

In a rotated sorted array, only one of A and B can be guaranteed to be sorted. If the element lies within a part which is sorted, then the solution is simple: just perform the search as if you were doing a normal binary search. If, however, you must search an unsorted part, then just recursively call your search function on the non-sorted part.

This ends up giving on a time complexity of O(lg n).

(Realistically, I would think that such a data structure would have a index accompanying it to indicate how many positions the array has been rotated.)

Edit: A search on Google takes me to this somewhat dated (but correct) topic on CodeGuru discussing the same problem. To add to my answer, I will copy some pseudocode that was given there so that it appears here with my solution (the thinking follows the same lines):

Search(set):     if size of set is 1 and set[0] == item          return info on set[0]     divide the set into parts A and B     if A is sorted and the item is in the A's range         return Search(A)     if B is sorted and the item is in the B's range         return Search(B)     if A is not sorted         return Search(A)     if B is not sorted         return Search(B)     return "not found" 

Answer 2

O(log(N))

Reduced to the problem of finding the largest number position, which can be done by checking the first and last and middle number of the area, recursively reduce the area, divide and conquer, This is O(log(N)) no larger than the binary search O(log(N)).

EDIT: For example, you have

6 7 8 1 2 3 4 5   ^       ^     ^  

By looking at the 3 numbers you know the location of the smallest/largest numbers (will be called mark later on) is in the area of 6 7 8 1 2, so 3 4 5 is out of consideration (usually done by moving your area start/end index(int) pointing to the number 6 and 2 ).

Next step,

6 7 8 1 2   ^   ^   ^   

Once again you will get enough information to tell which side (left or right) the mark is, then the area is reduced to half again (to 6 7 8).

This is the idea: I think you can refine a better version of this, actually, for an interview, an OK algorithm with a clean piece of codes are better than the best algorithm with OK codes: you 'd better hand-on some to heat-up.

Good luck!