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.

@Thilo: As in the array elements can move around, so long as they stay in the same relative order (going off one end means you just go to the other end). For example, the arrays `[1 2 3 4]`, `[2 3 4 1]`, `[3 4 1 2]`, and `[4 1 2 3]` are all the same array, just rotated around. — Andrew Song, Dec 10 '09 at 05:50
Of course, you deleted your comment. But I'll leave mine in case others need clarification. — Andrew Song, Dec 10 '09 at 05:51
Greek and @Andrew, do we initially know that by what number of elements array has been rotated? — Vikram, Nov 17 '13 at 05:27

score 40 · Accepted Answer · answered Dec 10 '09 at 05:45

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"

+1 to the point that in a real project, a marker will be always maintained. — Dr. Xray, Dec 10 '09 at 05:47
How do you determine that a part is sorted in less than O(n)? — Svante, Dec 10 '09 at 19:44
Answer to my question: you only need to compare the first and the last element. — Svante, Dec 10 '09 at 19:47
If elements are allowed to repeat there is an Omega(n) lower bound. Consider an array where all are 0, except one element, which is 1. — , Feb 06 '11 at 06:10

Dr. Xray · Answer 2 · 2009-12-10T16:05:33.663

18

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!

edited Dec 10 '09 at 16:05

answered Dec 10 '09 at 05:30

Dr. Xray

918
1
9
21

X - Can you please give an example of what you are saying. – Geek Dec 10 '09 at 05:56
Ok, I saw Andrew gave you the codes, combine with the example here, you should be able to work it out. – Dr. Xray Dec 10 '09 at 16:09
This assumes the input is `6 7 8 1 2 3 4 5` and target is `8`. These are the inputs from the example in the question above. – Scott Coates Nov 01 '17 at 16:26
Counterexample: search `1` in `0 1 0 0 0`. We don't know which half to dismiss. – Leonid Vasilev Apr 05 '18 at 08:56

score 8 · Answer 3 · answered Apr 21 '10 at 02:30

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.

You need to have if (arr[start] == number) return true; after if (start>end) and change if (start>end) to if (start>=end) — Dejell, May 07 '13 at 21:10
SO your code just returns the presence of key (true/fasle). But the question is to return the actual index of the key present in array. — Balaji Boggaram Ramanarayan, Oct 09 '13 at 20:56

score 5 · Answer 4 · answered Nov 02 '14 at 03:05

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

score 4 · Answer 5 · edited Nov 29 '11 at 18:17

4

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)

edited Nov 29 '11 at 18:17

Anne

26,765
9
65
71

answered Nov 29 '11 at 18:16

Prateek Caire

41
1

Sergey · Answer 6 · 2012-10-11T22:12:11.420

You can wrap an array with a class that only exposes

E get(int index);

and would behave as regular sorted array. For ex if you have 4 5 1 2 3 4, wrapper.get(0) will return 1.

Now you can just reuse binary search solution.

Wrapper can look like that:

class RotatedArrayWrapper<T> {
  int startIndex;
  private final List<T> rotatedArray;

  public RotatedArrayWrapper(List<T> rotatedArray) {
    this.rotatedArray = rotatedArray;
    //find index of the smalest element in array
    //keep in mind that there might be duplicates
    startIndex = ... 
  } 

  public T get(int index) {
    int size = rotatedArray.size();
    if (index > size) throw Exception...

    int actualIndex = (startIndex + index) % size;
    return rotatedArray.get(actualIndex);
  }
}

score 2 · Answer 7 · edited Nov 09 '11 at 01:01

2

Here is my approach at it:

public static int findMin(int[] a, int start, int end){
  int mid = (start + end)/2;
  if(start == mid){
    return a[mid+1];
  }else if(a[start] > a[mid]){
    return findMin(a, start, mid);
  }else if(a[mid+1] > a[start]){
    return findMin(a, mid+1, end);
  }else{
    return a[mid+1];
  }
}

Time complexity: O(log n)

edited Nov 09 '11 at 01:01

sth

222,467
53
283
367

answered Nov 09 '11 at 00:48

Kiran

21
2

3

Fails for the case [4,4,4,4,4,4,4,5,4,4] – lprsd May 17 '12 at 12:12
Yes. I tested it too. It fails when a value doubles in array – Sabri Meviş Oct 29 '15 at 11:51

score 1 · Answer 8 · answered Dec 06 '12 at 06:37

Python implementation. Could use to be more pythonic:

from bisect import bisect_left


def index(a, x):
    """Binary search to locate the leftmost value exactly equal to x.
    see http://docs.python.org/2/library/bisect.html#searching-sorted-lists

    >>> index([5, 14, 27, 40, 51, 70], 27)
    2
    >>> index([1, 2, 3, 4], 10)
    Traceback (most recent call last):
        ...
    ValueError
    """
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError


def _index_shifted(value, sequence, start, stop):
    """Recursive reset location and binary search"""
    # if at reset (min) and it's not the value, it's not there
    if start == stop and sequence[start] != value:
        return -1
    mid = (stop + start) // 2
    # check mid, since we are already here
    if sequence[mid] == value:
        return mid
    # right side is sorted
    elif sequence[mid] < sequence[stop]:
        # if value falls in range, search righ
        if sequence[stop] >= value > sequence[mid]:
            return index(sequence[mid:stop + 1], value) + mid
        # partition left side
        return _index_shifted(value, sequence, start, mid)
    # left side is sorted
    else:
        # if value falls in range, search left
        if sequence[mid] > value >= sequence[start]:
            return index(sequence[start:mid], value) + start
        # partition right side
        return _index_shifted(value, sequence, mid + 1, stop)


def index_shifted(sequence, value):
    """Returns index of value in a shifted sorted sequence; -1 if not present.

    >>> index_shifted([10, 13, 16, 19, 22, 25, 28, 31, 34, 37], 10)
    0
    >>> index_shifted([10, 13, 16, 19, 22, 25, 28, 31, 34, 37], 37)
    9
    >>> index_shifted([34, 37, 10, 13, 16, 19, 22, 25, 28, 31], 10)
    2
    >>> index_shifted([34, 37, 10, 13, 16, 19, 22, 25, 28, 31], 37)
    1
    >>> index_shifted([34, 37, 10, 13, 16, 19, 22, 25, 28, 31], 13)
    3
    >>> index_shifted([34, 37, 10, 13, 16, 19, 22, 25, 28, 31], 25)
    7
    >>> index_shifted([25, 28, 31, 34, 37, 10, 13, 16, 19, 22], 10)
    5
    >>> index_shifted([25, 28, 31, 34, 37, 10, 13, 16, 19, 22], -10)
    -1
    >>> index_shifted([25, 28, 31, 34, 37, 10, 13, 16, 19, 22], 100)
    -1
    """
    return _index_shifted(value, sequence, 0, len(sequence) - 1)

score 1 · Answer 9 · answered Apr 18 '17 at 20:13

My solution: efficiency: O(logn)

public static int SearchRotatedSortedArray(int l, int d, int[] array, int toFind) {
    if (l >= d) {
        return -1;
    }
    if (array[l] == toFind) {
        return l;
    }
    if (array[d] == toFind) {
        return d;
    }

    int mid = (l + d) / 2;
    if (array[mid] == toFind) {
        return mid;
    }

    if ((array[mid] > toFind && toFind > array[l]) || (array[mid] < toFind && array[d] < toFind)) {
        return SearchRotatedSortedArray(l, mid - 1, array, toFind);
    } else {
        return SearchRotatedSortedArray(mid + 1, d, array, toFind);
    }

}

score 0 · Answer 10 · edited Jul 20 '12 at 20:08

//this solution divides the array in two equal subarrays using recurssion and apply binary search on individual sorted array and it goes on dividing unsorted array

public class SearchRotatedSortedArray
{
    public static void main(String... args)
    {
        int[] array={5,6,1,2,3,4};

        System.out.println(search(array,Integer.parseInt(args[0]),0,5));
    }

    public static boolean search(int[] array,int element,int start,int end)
    {   
    if(start>=end)
    {
        if (array[end]==element) return true;else return false;
    }

    int mid=(start+end)/2;
    if(array[start]<array[end])
    {
        return binarySearch(array,element,start,end);
    }

    return search(array,element,start,mid)||search(array,element,mid+1,end);    
}

    public static boolean binarySearch(int[] array,int element,int start,int end)
    {
        int mid;

        while(start<=end)
        {
            mid=(start+end)/2;

            if(array[mid]==element)
            return true;

            if(array[mid]<element)
            {
                start=mid+1;

            }
            else
            {
                end=mid-1;

            }
        }

        return false;
    }
}

Here: search(array,element,start,mid)||search(array,element,mid+1,end) you can check which size to validate — Dejell, May 08 '13 at 07:56

score 0 · Answer 11 · answered Aug 05 '12 at 23:41

int findIndexInRotatedSort( vector<int> input, int s, int e, int toFind )
    {
        if (s > e || s >= input.size() || e < 0)
        {
            return -1;
        }

        int m = (s + e)/2;

        int sVal = input.at(s);
        int eVal = input.at(e);
        int mVal = input.at(m);

        if (sVal == toFind)
            return s;
        if (eVal == toFind)
            return e;
        if (mVal == toFind)
            return m;

        bool isFirstOrdered = (sVal < mVal);
        bool isSecondOrdered = (mVal < eVal);
        if (toFind > mVal)
        {
            if (!isSecondOrdered || toFind < eVal)
            {
                return findIndexInRotatedSort( input, m+1, e, toFind );
            }
            else
            {
                return findIndexInRotatedSort( input, s, m-1, toFind );
            }
        }
        else
        {
            if (!isFirstOrdered || toFind > sVal)
            {
                return findIndexInRotatedSort( input, s, m-1, toFind );
            }
            else
            {
                return findIndexInRotatedSort(  input, m+1, e, toFind );
            }
        }
    }

At StackOverflow please don not just paste code, but also explain your approach. In this specific case you may also have to explain what your answer adds to the answers already given (and accepted). — Gert Arnold, Aug 06 '12 at 00:18

score 0 · Answer 12 · edited Jul 04 '13 at 00:45

public class RoatatedSorted {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub

    int[] rotArray = {5,6,7,8,9,10,15,16,17,1,2,3,4,};

    search(rotArray,0,rotArray.length-1,10);

}

private static void search(int[] a, int low, int high,int key) {

    //int mid =  low + (high-low)/2;
    //if(a[mid]==a[key]){System.out.println("element found at" + key+1 +" position"); return;}

    // find pos to split array
    int pos = findSplitIndex(a,low,high);
    System.out.println("split pos found at" + pos +" position");


    if(key>=a[low]&& key <=a[pos])
        bsearch(a,low,pos,key);
    if(key>=a[pos+1]&& key <=a[high])
        bsearch(a,pos+1,high,key);  
}


private static void bsearch(int[] a, int low, int high,int key) {
    // TODO Auto-generated method stub
    if(low>high) return;
    int mid =  low + (high-low)/2;
    if(a[mid]==key)
    {System.out.println("element found at" + ++mid +" position"); return;}
    if(a[mid] > key)
        bsearch(a,low,mid-1,key);
    if(a[mid]<key)
        bsearch(a,mid+1,high,key);
}

private static int findSplitIndex(int[] a, int low, int high) {
    // TODO Auto-generated method stub
    int mid;
    if(low>high)return -1;
    while(true) {
        mid =  low + (high-low)/2;
    if( a[mid]>a[mid+1])
    break;


    if(a[mid]>a[low])
        low=mid;
    if(a[high]>a[mid])
        high=mid;
}
    return mid;


}

}

I've never been a fan of infinite loops: while( true ) for instance. I believe the findSplitIndex() can get stuck in this loop if a sorted array is passed into it as mid will calculate the middle index value and never change so the break will never happen. — , Oct 28 '19 at 19:34

score 0 · Answer 13 · answered Jul 16 '13 at 08:14

First to find the Minimum element in the array then divide array in two part. After that search the given value using Binary search tree. Complexity : O(logn) If you have to find the Minimum element in the rotated Array, use same approach,just skip Binary search. Complexity : O(logn)

//Search an element in a sorted and pivoted array
    class SearchInPivotedSortedArray
    {
        //searchInOrtedPivotedArray : Return index of matched element with given value.
        public static int searchInSortedPivotedArray(int[] A, int value)
        {
            int min = findMinElement(A,0,A.Length-1);
            if (min == A[0])
               return binarySearchTree(A, 0, A.Length-1, value);


            if (value <= A[A.Length-1])
               return binarySearchTree(A, min, A.Length-1, value);
            else
               return binarySearchTree(A, 0, min-1, value);


        }
        //return index of Pivot element
        public static int findMinElement(int[] Array, int low, int high)
        {

            if (low >= high)
                return low;

            int mid = (low + high) / 2;
            if (mid > low && Array[mid] < Array[mid - 1])
                return mid;
            if (mid < high && Array[mid] > Array[mid + 1])
                return mid + 1;

            if (Array[mid] < Array[high])
                return findMinElement(Array, low, mid - 1);

            return findMinElement(Array, mid + 1, high);

        }
        //Return match element index, if not found return -1
        public static int binarySearchTree(int[] array, int low, int high,int value)
        {
            if (low > high)
                return -1;
            int mid = (low + high)/2;

            if (array[mid] == value)
                return mid;
            if (array[mid] > value)
                return binarySearchTree(array, low, mid - 1, value);
            else
                return binarySearchTree(array, mid + 1, high, value);

        }
    }

score 0 · Answer 14 · answered Dec 09 '13 at 03:11

this is a O(logn) solution: tested. it works on both sorted and rotated sorted arrays:

public static int rbs(int[] a, int l, int r, int t) {

    if (a[l] <= a[r]) {
        return bs(a, l, r, t);
    }

    if (r < l) {
        return -1;
    } else {
        int m = (l+r) / 2;
        if (a[m] == t) {
            return m;
        } else if (a[m] > t) { // check left half
            if (a[l] > a[m]) { // left is unsorted
                return rbs(a, l, m-1, t);
            } else { // left is sorted
                if (a[l] < t) { // t is in range
                    return bs(a, l, m-1, t);
                } else if (a[l] > t) { // t is out of range on left
                    if (a[r] >= t) {
                        return rbs (a, m+1, r, t);
                    } else
                        return -1;
                } else
                    return l;
            }
        } else { // other side
            if (a[r] < a[m]) { // right is unsorted
                return rbs(a, m+1, r, t);
            } else { // right is sorted
                if (a[r] > t) { // t is in range
                    return bs(a, m+1, r, t);
                } else if (a[r] < t) { // t is out of range on right side
                    if (a[l] <= t) {
                        return rbs (a, l, m-1, t);
                    } else
                        return -1;
                } else
                    return r;
            }
        }
    }
}


public static int bs(int[] a, int l, int r, int t) {

    int m = (l+r) / 2;

    if (r < l) {
        return -1;
    } else {
        if (a[m] == t)
            return m;
        else if (a[m] < t)
            return bs(a, m+1, r, t);
        else
            return bs (a, l, m-1, t);
    }
}

score 0 · Answer 15 · answered May 01 '14 at 21:14

Try out this solution,

     public static int findElement(int[] a, int key, int left, int right) {

           if (left > right) {
              return -1;
           }

           int mid = (left + right) / 2;

           if (key == a[mid]) {
              return mid;
           } else if (key < a[mid]) {
              return (a[left] <= a[mid] && a[left] < key ? findElement(
                a, key, left, mid - 1) : findElement(a, key,
                mid + 1, right));
           } else {
              return (a[mid] <= a[right] && a[right] < key ? findElement(
                a, key, left, mid - 1) : findElement(a, key,
                mid + 1, right));
    }

}

score 0 · Answer 16 · answered Sep 12 '14 at 14:46

Here is a C++ implementation of @Andrew Song's answer

int search(int A[], int s, int e, int k) {
    if (s <= e) {
        int m = s + (e - s)/2;
        if (A[m] == k)
            return m;
        if (A[m] < A[e] && k > A[m] && k <= A[e]) 
            return search(A, m+1, e, k);
        if (A[m] > A[s] && k < A[m] && k >= A[s]) 
            return search(A, s, m-1, k);
        if (A[m] < A[s]) 
            return search(A, s, m-1, k);
        if (A[m] > A[e])
            return search(A, m+1, e, k);
    }
    return -1;
}

score 0 · Answer 17 · answered Jan 26 '16 at 18:16

This is 100% working and tested solution in PYTHON

Program to find a number from a sorted but rotated array

def findNumber(a, x, start, end):
  if start > end:
    return  -1
  mid = (start + end) / 2
  if a[mid] == x:
    return mid
  ## Case : 1  if a[start] to a[mid] is sorted , then search first half of array
  if a[start] < a[mid]:
    if (x >= a[start] and x <= a[mid]):
      return findNumber(a, x, start, mid - 1)
    else:
      return findNumber(a,x, mid + 1, end)
  ## Case: 2 if a[start] to a[mid] is not sorted , then a[mid] to a[end] mist be sorted
  else:
    if (x >= a[mid] and x <= a[end]):
      return findNumber(a, x, mid + 1, end)
    else:
      return findNumber(a,x, start, mid -1)


a = [4,5,6,7,0,1,2]
print "Your array is  : " , a
x = input("Enter any number to find in array : ")
result = findNumber(a, x, 0, len(a) - 1)
print "The element is present at %d position: ", result

score 0 · Answer 18 · answered Apr 05 '18 at 13:36

In worst case you have to use linear search and examine whole array to find a target, because, unlike a set, an array may contain duplicates. And if an array contains duplicates you can't use binary search in the given problem.

If queries on particular array are infrequent you can use standard binary search if whole array is sorted (first element is strictly smaller than last element) and use linear search otherwise. For more information see How fast can you make linear search? discussion on StackOverflow and 10 Optimizations on Linear Search article by Thomas A. Limoncelli.

Hovewer, if queries are frequent you can sort input array in linear time (see Fastest algorithm for circle shift N sized array for M position discussion on StackOverflow) in preprocessing step and use standard binary search as usual.

score -1 · Answer 19 · answered Aug 12 '13 at 20:42

Find element index in rotated sorted array

Example : [6,7,8,1,2,3,5]

int findElementIndex(int []a, int element, int start, int end)
{
    int mid = (start + end)>>1;

    if(start>end)
        return -1;

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

    if(a[mid] < a[start])
    {
       if(element <= a[end] && element > a[mid])
        {
       return findElementIndex(a,element,mid+1,end);
        }
        else{
       return findElementIndex(a,element,start,mid-1);
        }
     }
    else  if(a[mid] > a[start]){
        if(element >= a[start] && element < a[mid])
             return findElementIndex(a,element,start,mid-1);
        else
            return findElementIndex(a,element,mid+1,end);
    }
    else if (a[mid] == a[start]){
        if(a[mid] != a[end]) // repeated elements
          return findElementIndex(a,element,mid+1,end);
        else
            int left = findElementIndex(a,element,start,mid-1);
            int right = findElementIndex(a,element,mid+1,end);

            return (left != -1) ? left : right;

    }

}

Maxximus · Answer 20 · 2012-01-05T13:47:38.327

#include<iostream>
using namespace std;
int BinarySearch(int *a,int key, int length)
{
    int l=0,r=length-1,res=-1;
    while(l<=r)
    {
        int mid = (l+r)/2;
        if(a[mid] == key) {res = mid; break;}
                //Check the part of the array that maintains sort sequence and update index                   
                // accordingly.
        if((a[mid] < a[r] && ( key > a[mid] && key <=a[r]))
            || a[mid] > a[r] && !( key>=a[l] && key <a[mid]))
        {
                     l = mid+1;
        }
        else r = mid-1;
    }
    return res;
}
void main()
{
    int arr[10] = {6,7,8,9,10,13,15,18,2,3};
    int key = 8;
    cout<<"Binary Search Output: "<<BinarySearch(arr,key,10);
}

The program above divides the problem size by 2 every time by searching that part of the array that can possibly contain the search element. — Maxximus, Oct 08 '12 at 11:15

Searching a number in a rotated sorted Array

20 Answers20

Linked

Related