1. 原题链接
https://leetcode.com/problems/search-in-rotated-sorted-array/description/
2. 题目要求
给定一个按升序排列的数组nums[ ]和目标值target，将数组在某点处进行旋转，然后在旋转后的数组中查找与target相同的元素，存在返回其下标，不存在返回“-1”。
注意：旋转点未知！
例，{1, 2, 3, 4, 5, 6, 7}旋转后可能为：
{4, 5, 6, 7，1，2, 3}
{3, 4, 5, 6, 7，1，2}
{6，7，1, 2, 3, 4, 5}
......
3. 解题思路
思路一：暴力解决，遍历数组进行匹配，时间复杂度为O( n );
思路二：巧妙利用旋转数组
（1）旋转数组的性质：旋转后的数组由两段按升序排列的数组组成。
（2）先找出旋转点，旋转点左右两边都是按升序排列的数组；
（3）然后判断target在旋点的左边还是右边：用target和左右两边两个升序数组的最后一位进行比较，即可知道target在哪一边；
（4）利用折半查找法进行查找。找到返回元素所在下标，否则返回-1。
时间复杂度为O( logn )
例如，target =4 ，旋转后的数组为{4, 5, 6, 7，1，2, 3}，首先找到旋转点“1”。target = 4>3，所以target =4在左半边。然后在左半边进行折半查找，返回查找结果。
4. 代码实现
1 public class SearchInRotatedSortedArray { 2 public static void main(String[] args) { 3 SearchInRotatedSortedArray si = new SearchInRotatedSortedArray(); 4 int[] nums1 = {}; 5 int[] nums2 = {4, 5, 6, 7, 0, 1, 2}; 6 System.out.println(si.search(nums1, 5)); 7 System.out.println(si.search(nums2, 5)); 8 } 9 10 public int search(int[] nums, int target) { 11 if (nums.length == 0) return -1; // 数组为空返回 -1 12 int pivot = findMinIdx(nums); 13 if (target == nums[pivot]) return pivot; // target恰好等于旋转点未知的元素，直接返回 14 int len = nums.length; 15 int start, end; 16 17 /** 18 * 采用二分法进行查找 19 */ 20 if (target > nums[len - 1]) { 21 start = 0; 22 end = pivot; 23 } else { 24 start = pivot; 25 end = len - 1; 26 } 27 28 while (start <= end) { 29 int mid = start + (end - start) / 2; 30 if (nums[mid] == target) return mid; 31 else if (target > nums[mid]) start = mid + 1; 32 else end = mid - 1; 33 } 34 return -1; // 不存在target返回-1 35 } 36 37 // 找出旋转点 38 public int findMinIdx(int[] nums) { 39 int start = 0, end = nums.length - 1; 40 while (start < end) { 41 int mid = start + (end - start) / 2; 42 if (nums[mid] > nums[end]) 43 start = mid + 1; 44 else end = mid; 45 } 46 return start; 47 } 48 }
运行结果：
