LeetCode Online Judge 题目C# 练习 - 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.

 1         public static int SearchinRotatedSortedArray(int[] A, int target)
 2         {
 3             return BinarySearchRotatedSortedArray(A, 0, A.Length - 1, target);
 4         }
 5 
 6         public static int BinarySearchRotatedSortedArray(int[] A, int l, int r, int target)
 7         {
 8             if (l > r)
 9                 return -1;
10 
11             int m = (l + r) / 2;
12 
13             if (target == A[m])
14                 return m;
15 
16             if (A[m] >= A[l])
17             {
18                 if (target >= A[l] && target < A[m])
19                     r = m - 1;
20                 else
21                     l = m + 1;
22 
23                 return BinarySearchRotatedSortedArray(A, l, r, target);
24             }
25             else
26             {
27                 if (target > A[m] && target <= A[r])
28                     l = m + 1;
29                 else
30                     r = m - 1;
31 
32                 return BinarySearchRotatedSortedArray(A, l, r, target);
33             }
34         }

代码分析：

　　同样是binary search 的变形。每次往下找，到底是找 前半部 还是 后半部， 要根据情况两种情况。

　　1. A[m] >= A[l], 前半部分是sorted的。

　　2. A[m] < A[l]， 后半部分是sorted的。