Leetcode 33: Search in Rotated Sorted Array

Suppose an array sorted in ascending order 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 class Solution {
 2     public int Search(int[] nums, int target) {
 3         return BinarySearch(nums, target, 0, nums.Length - 1);        
 4     }
 5     
 6     private int BinarySearch(int[] nums, int target, int start, int end)
 7     {
 8         if (start > end) return -1;
 9         if (start == end) return nums[start] == target ? start : -1;
10         
11         int mid = start + (end - start) / 2;
12         
13         if (nums[mid] == target) return mid;
14         
15         if (nums[start] < nums[mid])
16         {
17             if (nums[start] <= target && target <= nums[mid])
18             {
19                 return BinarySearch(nums, target, start, mid - 1);
20             }
21             else
22             {
23                 return BinarySearch(nums, target, mid + 1, end);
24             }
25         }
26         else
27         {            
28             if (nums[mid + 1] <= target && target <= nums[end])
29             {
30                 return BinarySearch(nums, target, mid + 1, end);
31             }
32             else
33             {
34                 return BinarySearch(nums, target, start, mid - 1);
35             }
36         }
37         
38         return -1;
39     }
40     
41     
42 }

Leetcode 33: Search in Rotated Sorted Array

推荐阅读