搜索旋转排序数组

题目描述

给定一个按升序排列、且其中元素互不相同的整数数组 nums。在传递给你之前，nums 在预先未知的某个下标 k 处发生了旋转，使数组变为：

[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]

给定旋转后的数组 nums 和一个整数 target，如果 target 存在于数组中，返回它的下标；否则返回 -1。

你需要设计一个时间复杂度为 O(log n) 的算法。

输入格式

第一行输入两个整数 n 和 target。

第二行输入 n 个整数，表示数组 nums。

输出格式

输出一个整数，表示 target 在数组中的下标；如果不存在，输出 -1。

数据范围

1 <= n <= 5000

-10^4 <= nums[i], target <= 10^4

nums 中所有元素互不相同。

样例 1

输入

7 0
4 5 6 7 0 1 2

输出

4

样例 2

输入

7 3
4 5 6 7 0 1 2

输出

-1

样例 3

输入

1 0
1

输出

-1