leetcode 33：搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。 你可以假设数组中不存在重复的元素。 你的算法时间复杂度必须是 O(log n) 级别。 示例 1: 输入: nums =[4,5,6,7,0,1,2], target = 0 输出: 4 示例 2: 输入: nums = [4,5,6,7,0,1,2],target = 3 输出: -1
思路： 看到排序数组中查找，我们第一时间想到的就是二分查找，也只有二分查找能达到log n的时间复杂度了，但是这个一个旋转过的排序数组，我们该如何寻找它与排序数组之间的共同点呢？
我们可以观察到对于 nums = [4,5,6,7,0,1,2]，我们直接进行二分查找的思路，找到的中点是 7，可以发现，7左边都是已排序的数组（包括7），7右边是部分有序的数组（也是一个旋转排序数组）（不包括7），因此，我们可不可以得出这样一个结论，如果中点的数比最右边的数要小，则7 左边的数组有序，右边的还是一个旋转排序数组，否则 7 左边的是一个旋转排序数组，右边是一个排序数组。
public int search(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int start = 0; int end = nums.length - 1; return mySearch(nums, target, start, end); } private int mySearch(int[] nums, int target, int start, int end) { if(start < 0 || end <0){ return -1; } // 处理边界 if (end < start) { return -1; } if (end == start) { return nums[start] == target ? start : -1; } int mid = (end + start) / 2; if (nums[mid] > nums[end]) { // 左边有序，右边无序 int result = -1; if (target <= nums[mid] && target >= nums[start]) { result = Arrays.binarySearch(nums, start, mid + 1, target); if(result <0){ result = -1; } } else { result = mySearch(nums, target, mid + 1, end); } return result; }else{ // 左边无序，右边有序 int result = -1; if(target <= nums[end] && target >= nums[mid]){ result = Arrays.binarySearch(nums,mid,end+1,target); if(result <0){ result = -1; } }else{ result = mySearch(nums,target,start,mid-1); } return result; } }