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.
» Solve this problem[解题思想]
同样是二分，难度主要在于左右边界的确定。需要结合两个不等式：
1. A[m] ? A[left]
2. A[m] ? target
具体逻辑看code。
[Code]
1: int search(int A[], int n, int target) {
2: // Start typing your C/C++ solution below
3: // DO NOT write int main() function
4: int l = 0, r = n-1;
5: while(l<=r)
6: {
7: int m = (l+r)/2;
8: if(A[m] == target) return m;
9: if(A[m]>= A[l])
10: {
11: if(A[l]<=target && target<= A[m])
12: r=m-1;
13: else
14: l = m+1;
15: }
16: else
17: {
18: if(A[m] >= target || target>= A[l])
19: r = m-1;
20: else
21: l = m+1;
22: }
23: }
24: return -1;
25: }
Update 08/23/2014
See the comments from reader. Add a graph and also change the code a bit for readability(See highlight code in red).
The general idea is, to use some in-equations to distinguish below 3 conditions, and decide the new range of binary search.
1: int search(int A[], int n, int target) {
2: int l = 0, r = n-1;
3: while(l<=r)
4: {
5: int m = (l+r)/2;
6: if(A[m] == target) return m;
7: if(A[m]>= A[l])
8: {
9: if(A[l]<=target && target< A[m])
10: r=m-1;
11: else
12: l = m+1;
13: }
14: else
15: {16: if(A[m]< target && target<=A[r])
17: l = m+1;
18: else
19: r = m-1;
20: }
21: }
22: return -1;
23: }