-
Difficulty: Medium
-
Related Topics: Array, Binary Search
-
Link: https://leetcode.com/problems/search-in-rotated-sorted-array/
Description
You are given an integer array nums
sorted in ascending order, and an integer target
.
给定一个升序排序的整数数组 nums
,和另一个整数 target
。
Suppose that nums
is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7]
might become [4,5,6,7,0,1,2]
).
假设之前 nums
在某处你不知道的地方发生了旋转(也就是说,[0, 1, 2, 4, 5, 6, 7]
可能会变成 [4, 5, 6, 7, 0, 1, 2]
)。
If target
is found in the array return its index, otherwise, return -1
.
如果 target
存在于 nums
中,返回其下标,否则返回 -1
。
Examples
Example 1
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3
Input: nums = [1], target = 0
Output: -1
Constraints
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
- All values of
nums
are unique. -
nums
is guranteed to be rotated at some pivot. -10^4 <= target <= 10^4
Solution
这题的关键,在于摆脱这个旋转数组的限制使用二分搜索。以下解法来自 discussion,算是个人认为比较好理解的一种方法了。该方法的核心在于两次二分查找,第一次找到数组发生旋转的那个点,第二次执行常规的二分搜索,具体解法见下:
class Solution {
fun search(nums: IntArray, target: Int): Int {
var left = 0
var right = nums.lastIndex
// 第一步:找到旋转的点
while (left < right) {
val mid = left + (right - left) / 2
if (nums[mid] > nums[right]) {
left = mid + 1
} else {
right = mid
}
}
val pivot = left
left = 0
right = nums.lastIndex
// 找到 pivot 后,剩下的为常规的二分搜索
while (left <= right) {
val mid = left + (right - left) / 2
val realMid = (mid + pivot) % nums.size
when {
nums[realMid] == target -> return realMid
nums[realMid] < target -> left = mid + 1
else -> right = mid - 1
}
}
return -1
}
}