题目:搜索旋转排序数组
整数数组nums按升序排列，数组中的值互不相同。
在传递给函数之前，nums在预先未知的某个下标k（0 <= k < nums.length）上进行了 旋转，使数组变为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标从 0开始 计数）。
例如，[0,1,2,4,5,6,7]在下标3处经旋转后可能变为[4,5,6,7,0,1,2]。
给你旋转后的数组nums和一个整数target，如果nums中存在这个目标值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- 进阶：
进阶：你可以设计一个时间复杂度为 O(log₂n) 的解决方案吗？思路
对于有序数组，可以使用二分查找的方法查找元素。
但是这道题中，数组本身不是有序的，进行旋转后只保证了数组的局部是有序的，这还能进行二分查找吗？答案是可以的。
可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从6这个位置分开以后数组变成了[4, 5, 6]和[7, 0, 1, 2]两个部分，其中左边[4, 5, 6]这个部分的数组是有序的，其他也是如此。
这启示我们可以在常规二分查找的时候查看当前mid为分割位置分割出来的两个部分[l, mid]和[mid+1, r]哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出target在不在这个部分：
- 如果
[l, mid-1]是有序数组，且target的大小满足[nums[l],nums[mid-1]],则我们应该将搜索范围缩小至[l, mid-1]，否则在[mid+1, r]中寻找。 - 如果
[mid+1, r]是有序数组，且target的大小满足[nums[mid+1],nums[r]]，则我们应该将搜索范围缩小至[mid+1, r]，否则在[l, mid-1]中寻找。
通俗来讲就是:将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也可能是部分有序。
此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.
- 时间复杂度:O(log₂n)
- 空间复杂度:O(1)
代码
public int search(int[] nums, int target) { // 总时间复杂度O(log₂n)
// 如果长度为0,直接返回-1
if (nums.length == 0) {
return -1;
}
// 如果长度为1,检查与目标值是否相等,如果相等返回0,否则直接返回-1
if (nums.length == 1) {
return nums[0] == target ? 0 : -1;
}
int low = 0;
int high = nums.length - 1;
while (low <= high) { // 时间复杂度O(log₂n)
int mid = low + (high - low) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[low] <= nums[mid]) { // 左半部分有序
// target在左半部分
if (nums[low] <= target && target <= nums[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
} else { // 右半部分有序
// target在右半部分
if (nums[mid] <= target && target <= nums[high]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
return -1;
}
