Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,
0 1 2 4 5 6 7might become4 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.
Analysis
Take “4 5 6 7 0 1 2” as an example. The mid entry is 7. We can compare it with the first entry. If the first entry is smaller than the mid entry, then the first half (from 4 to 7) must be in strictly increasing order. So we can compare target with the first entry and the mid entry, then we can decide if the target is in this half or not. If the first entry is larger than the mid entry, then the second half (fron 7 to 2) is in strictly increasing order. We can compare the target with them. Using this algorithm, every time we can throw half of the array.
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
public class Solution { public int search(int[] A, int target) { int left = 0; int right = A.length - 1; while (left <= right) { int mid = (left + right) / 2; if (A[mid] == target) return mid; if (A[left] <= A[mid]) { if (target >= A[left] && target <= A[mid]) right = mid - 1; else left = mid + 1; } else { if (target >= A[mid] && target <= A[right]) left = mid + 1; else right = mid - 1; } } return -1; } } |
Complexity
The complexity is O(log n), which is similar to binary search.
Follow up
Find the rotation pivot.
Solution from leetcode.com.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
int FindSortedArrayRotation(int A[], int N) { int L = 0; int R = N - 1; while (A[L] > A[R]) { int M = L + (R - L) / 2; if (A[M] > A[R]) L = M + 1; else R = M; } return L; } |
For details, visit http://leetcode.com/2010/04/searching-element-in-rotated-array.html.