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.
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.
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 }
