Leetcode No.33 搜索旋转排序数组（二分法）
一、题目描述
升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。
请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
示例 1： 输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4
示例 2： 输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1
示例 3： 输入：nums = [1], target = 0 输出：-1
提示： 1 <= nums.length <= 5000 -10^4 <= nums[i] <= 10^4 nums 中的每个值都 独一无二 nums 肯定会在某个点上旋转 -10^4 <= target <= 10^4
二、解题思路
一个升序数组在经过旋转之后，可以得到下面可视化的折线图：
其中横轴表示数组元素的下标，纵轴表示数组元素的值。图中标出了最小值的位置，是我们需要查找的目标。
我们考虑数组中的最后一个元素 x：在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 x；而在最小值左侧的元素，它们的值一定都严格大于 x。
使用二分查找，初始化两个变量low=0,hight=nums.length-1
1、mid=(low+high)/2
2、假如nums[mid]等于target，返回下标mid
3、当nums[mid]小于nums[high]时，说明mid->high右侧是有序的，判断target是否在右侧，否则往左侧递归查找
4、当nums[mid]大于nums[high]时，说明low->mid左侧是有序的，判断target是否在左侧，否则往右侧递归查找
5、当low>high时，表示没有找到，返回-1
三、代码
class Solution {
public int search(int[] nums, int target) {
return search(nums, 0, nums.length - 1, target);
}
private int search(int[] nums, int low, int high, int target) {
if (low > high)
return -1;
int mid = (low + high) / 2;
if (nums[mid] == target)
return mid;
if (nums[mid] < nums[high]) {
//右侧是有序的
if (nums[mid] < target && target <= nums[high])
//目标值在右侧
return search(nums, mid + 1, high, target);
else
//目标值在左侧
return search(nums, low, mid - 1, target);
} else {
//左侧是有序的
if (nums[low] <= target && target < nums[mid])
//目标值在左侧
return search(nums, low, mid - 1, target);
else
//目标值在右侧
return search(nums, mid + 1, high, target);
}
}
}四、复杂度分析
时间复杂度：O(logN)，这里 N 是数组的长度，在递归一次排除一半，因此时间复杂度是对数级别的。 空间复杂度：O(1)，使用到的临时变量的个数是常数。
腾讯云开发者
