## Thursday, January 3, 2013

### [LeetCode] Search in 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.
» Solve this problem

[解题思想]

1. A[m] ? A[left]
2. A[m] ? target

[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

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:       }
``````