Searching a number in a rotated sorted Array

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.

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"

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!

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.

It a simple modification of normal binary search. In fact we it will work for both rotated and sorted arrays. In the case of sorted arrays it will end up doing more work than it really needs to however.

For a rotated array, when you split the array into two subarrays, it is possible one of those subarrays will not be in order. You can easily check if if each half is sorted by comparing the first and last value in the subarray.

Knowing whether each subarray is sorted or not, we can make a choice of what do do next.

1) left subarray is sorted, and the value is within the range of the left subarray (check both ends!)

Then search recursively search left subarray.

2) right subarray is sorted, and the value is within the range of the right subarray (check both ends!)

Then recursively search right subarray.

3) left is Not sorted

Then recursively search left subarray

4) Right is Not sorted

Then recursively search right subarray.

Note: the difference between this and a normal binary search is that we cannot simply choose the subarray to recurse on by simply comparing the last value left subarray (of first value of the right subarray) to make our decision. The value has to be strictly in the left or right subarray and that subarray has to sorted, otherwise we must recurse on the unsorted subarray.

Here is some Objective-C that implements this:

@implementation BinarySearcher

- (BOOL)isValue:(int)value inArray:(int[])array withArraySize:(int)size {

    return [self subSearchArray:array forValue:value fromIndex:0 toIndex:size -1];
}

- (BOOL)subSearchArray:(int[])array forValue:(int)value fromIndex:(int)left toIndex:(int)right {

    if (left <= right) {

        int middle = (left + right) / 2;

        BOOL leftArraySorted = array[left] <= array[middle];
        BOOL rightArraySorted = array[middle + 1] <= array[right];

        if (array[middle] == value) {
            return YES;
        } else if (leftArraySorted && value >= array[left] && value < array[middle]) {
            return [self subSearchArray:array forValue:value fromIndex:left toIndex:middle];
        } else if (rightArraySorted && value >= array[middle + 1] && value <= array[right]) {
            return [self subSearchArray:array forValue:value fromIndex:middle + 1 toIndex:right];
        } else if (!leftArraySorted) {
            return [self subSearchArray:array forValue:value fromIndex:left toIndex:middle];
        } else if (!rightArraySorted) {
            return [self subSearchArray:array forValue:value fromIndex:middle + 1 toIndex:right];
        }
    }

    return NO;
}

@end

At any index, one partition will be sorted and other unsorted. If key lies within sorted partition, search within sorted array, else in non sorted partition.

BS(lo, hi)
m = (lo + hi)/2
if(k = a[m])
    return m
b = 0
if(a[hi] > a[m])
    b = 1
if(b)
    if(k > a[m] && k<a[hi])
        BS(m+1, hi)
else
    BS(lo, m-1)

Searching a number in a rotated sorted Array

Related

Recent Posts