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

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!

Answer 2

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 3

I was asked this question in an interview recently.The question was describe an algorithm to search a "key" in a circular sorted array.I was also asked to write the code for the same. This is what I came up with:

Use divide and conquer binary search. For each subarray check if the array is sorted. If sorted use classic binary search e.g

data[start]< data[end] implies that the data is sorted. user binary else divide the array further till we get sorted array.

    public boolean search(int start,int end){
    int mid =(start+end)/2;
    if(start>end)
    {
        return  false;
    }
    if(data[start]<data[end]){
        return this.normalBinarySearch(start, end);
    }
    else{
        //the other part is unsorted.
        return (this.search(start,mid) ||
        this.search(mid+1,end));
    }
}

where normalBinarySearch is a simple binary search.