Search Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

The key idea is to know that there must be one half side is in normal order. Remember this, then the problem is easy to solve.

Java: SearchRotatedArray

01 public int search(int[] A, int target) {

02     return binarySearch(A,0,A.length-1,target);

03 }

04 

05 public int binarySearch(int []A, int start, int end, int target)

06 {

07     if(start>end)

08         return -1;

09     int mid=start+(end-start)/2;

10     if(A[mid]==target)

11     {

12         return mid;

13     }

14     else

15     {

16         if(A[start]<A[mid]) //first half is in order

17         {

18             if(target>=A[start]&&target<=A[mid]) //target in first half, just search that half

19             {

20                 return binarySearch(A,start,mid-1,target);

21             }

22             else //target in the second half, search it recursively

23             {

24                 return binarySearch(A,mid+1,end,target);

25             }

26         }

27         else if(A[start]>A[mid]) //first half is rotated, then second half is in order

28         {

29             if(target>=A[mid] && target<=A[end]) //target is in the second half

30             {

31                 return binarySearch(A,mid+1,end,target);

32             }

33             else //target is in the first half, search for it recursively

34             {

35                 return binarySearch(A,start,mid-1,target);

36             }

37         }

38         else //A[start]==A[mid], search the second half

39         {

40             return binarySearch(A,mid+1,end,target);

41         }

42         

43     }

44 }

Follow up for "Search in Rotated Sorted Array":

What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

If duplicates are allowed, the question becomes more tricky. We need to handle the duplication cases specially. See line 37 -- line 50.

Java: SearchRotatedArrayII

01 public boolean search(int[] A, int target) {
02     return binarySearch(A,0,A.length-1,target);
03 }
04 
05 public boolean binarySearch(int []A, int start, int end, int target)
06 {
07     if(start>end)
08         return false;
09     int mid=start+(end-start)/2;
10     if(A[mid]==target)
11     {
12         return true;
13     }
14   
15     if(A[start]<A[mid])
16     {
17         if(target>=A[start]&&target<=A[mid])
18         {
19             return binarySearch(A,start,mid-1,target);
20         }
21         else
22         {
23             return binarySearch(A,mid+1,end,target);
24         }
25     }
26     else if(A[start]>A[mid])
27     {
28         if(target>=A[mid] && target<=A[end])
29         {
30             return binarySearch(A,mid+1,end,target);
31         }
32         else
33         {
34             return binarySearch(A,start,mid-1,target);
35         }
36     }
37     else if(A[start]==A[mid])
38     {
39         if(A[mid]!=A[end])
40         {
41             return binarySearch(A,mid+1,end,target);
42         }
43         else
44         {                                  
45             boolean result=binarySearch(A,start,mid-1,target);
46             if(result==false)
47                 return binarySearch(A,mid+1,end,target);
48             else
49                 return result;                  
50         }
51       
52     }
53     return false;  
54 }