LeetCode: Search in Rotated Sorted Array II

搞了很久始终没通过，看了网上的简单答案，这道题的关键在于看target处于哪段递增区间里

 1 class Solution {
 2 public:
 3     bool search(int A[], int n, int target) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         int left, right, mid;
 7         left = 0, right = n-1;
 8         while (left <= right) {
 9             mid = (left+right)/2;
10             if (target == A[mid]) return true;
11             if (A[left] < A[mid]) {
12                 if (target >= A[left] && target < A[mid]) right = mid - 1;
13                 else left = mid + 1;
14             } else if (A[left] > A[mid]) {
15                 if (target > A[mid] && target <= A[right]) left = mid + 1;
16                 else right = mid - 1;
17             }
18             else left++;
19         }
20     }
21 };

 1 public class Solution {
 2     public bool Search(int[] nums, int target) {
 3         int left = 0, right = nums.Length - 1;
 4         while (left <= right) {
 5             int mid = (left + right) / 2;
 6             if (target == nums[mid]) return true;
 7             if (nums[left] < nums[mid]) {
 8                 if (target >= nums[left] && target < nums[mid]) right = mid - 1;
 9                 else left = mid + 1;
10             }
11             else if (nums[left] > nums[mid]) {
12                 if (target > nums[mid] && target <= nums[right]) left = mid + 1;
13                 else right = mid - 1;
14             }
15             else left++;
16         }
17         return false;
18     }
19 }

View Code