1.题目

整数数组 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 。请设计一个时间复杂度为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

示例 3：
输入：nums = [1], target = 0
输出：-1

提示：
1 <= nums.length <= 5000
-10⁴ <= nums[i] <= 10⁴
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10⁴<= target<= 10⁴

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array

2.思路

（1）二分搜索
设计一个时间复杂度为 O(log n) 的搜索方案，最容易想到的应该就是二分搜索，不过本题中的数组是经过一个升序数组”旋转“之后得到的，只是局部有序。所以在使用二分搜索时，关键在于分情况判断 target 所在的区间。

在第一趟的查找过程中，要确定查找区间的开头位置、中间位置以及结尾位置，这里分别定义变量 left、mid 和 right，并赋予相应的值。这三个变量将整个 nums 数组分为两个部分，即 nums[left…mid] 和 nums[mid…right]。

在 left <= right 成立的条件下，分情况进行讨论：

• 若 nums[mid] == target，直接返回 mid 即可；
• 若 nums[left] <= nums[mid]：
  • 如果 nums[left] <= target && target < nums[mid]：这说明 target 一定在 nums[left…mid] 之间，按照而二分查找的算法思想，此时的查找区间应变为 nums[left…mid]，并且 right = mid - 1，进行下一轮查找；
  • 如果 nums[left] > target || target >= nums[mid，这说明 target 在 nums[mid…right] 之间，left = mid + 1，进行下一轮查找；
• 若 nums[left] > nums[mid]：
  • 如果 nums[mid] < target && target <= nums[right]，这说明 target 在 nums[mid…right] 之间，同理变换区间进行查找。
  • 如果 nums[mid] >= target || target > nums[right]，这说明 target 在 nums[left…mid] 之间，同理变换区间进行查找。

相关题目：
LeetCode_二分搜索_中等_81.搜索旋转排序数组 II
LeetCode_二分搜索_中等_153.寻找旋转排序数组中的最小值
LeetCode_二分搜索_困难_154.寻找旋转排序数组中的最小值 II

3.代码实现（Java）

//思路1————二分搜索
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // nums[left...mid...high]
            if (nums[left] <= nums[mid]) {
	            // nums[left...mid] 有序
                if (nums[left] <= target && target < nums[mid]) {
                    // target 在 nums[left...mid] 中
                    right = mid - 1;
                } else {
                    // target 在 nums[mid...right] 中
                    left = mid + 1;
                }
            } else {
            	// nums[mid...right] 有序
                if (nums[mid] < target && target <= nums[right]) {
                    // target 在 nums[mid...right] 中  
                    left = mid + 1;
                } else {
                    // target 在 nums[left...mid] 中
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}