搜索旋转排序数组

题解思路

本题要求 $O(\log n)$ 的时间复杂度，因此我们必须使用 二分查找。

1. 旋转数组的特点

旋转数组由两个递增的子数组拼接而成，例如：

原数组:     [0, 1, 2, 4, 5, 6, 7]

Leetcode 66.搜索旋转排序数组-原题链接

题目内容

整数数组 $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)$的算法解决此问题。

输入描述

• 第一行输入一个整数 n，表示数组的长度。
• 第二行输入 n 个整数，表示旋转后的数组 nums。
• 第三行输入一个整数 target，表示需要查找的目标值。

输出描述

• 输出一个整数，表示目标值 target 在数组中的索引，若不存在则输出 -1。

样例

样例 1

输入

7
4 5 6 7 0 1 2
0

输出

4

样例 2

输入

7
4 5 6 7 0 1 2
3

输出

-1

样例 3

输入

1
1
0

输出

-1

提示：

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