Problem
1. Suppose a sorted array is rotated at some pivot unknown to you beforehand.
For example, 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.
2. Follow up: what if duplicates are allowed ?
Algorithm
1. No duplicates
Let's search the target in the subarray A[L to R], and let M = (L+R)/2,
Claim 1.
If A[M] > A[L], then A[L to M] is sorted.
If A[M] < A[R], then A[M to R] is sorted.
If A[L] < A[M] < A[R], then A[L to R] is sorted.
Claim 2.
If A[M] == target return M
Else If A[M] > A[L]
If A[L] < target < A[M], search A[L to M-1]
Else search A[M+1 to R]
Else
If A[M] < target < A[R], search A[M+1 to R]
Else search A[L to M-1]
2. Duplicates
When array has duplicates, as shown in figure below, using A[M] >= A[L] cannot distinguish the two cases. Since A[L] == A[M] != target, we can eliminate A[L], i.e. search in A[L+1 to R]. In case one, we finally will eliminate A[L to M], while in case two, finally A[L] != A[M]. So,
If A[M] == target return M
Else If A[M] > A[L]
If A[L] < target < A[M], search A[L to M-1]
Else search A[M+1 to R]
Else If A[M] < A[L]
If A[M] < target < A[R], search A[M+1 to R]
Else search A[L to M-1]
Else
search A[L+1, R]
Else
search A[L+1, R]
In the worst case, the algorithm needs O(n) time.
For example,
A = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,1,1,1,1]
and target = 3. We need to execute search A[L+1, R] O(n) times.
Better Idea ?
No comments:
Post a Comment