搜索旋转排序数组
🟡 中等题目描述
整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在预先未知的某个下标 k 上进行了旋转。给你旋转后的数组 nums 和一个整数 target，如果 nums 中存在这个目标值，返回它的下标，否则返回 -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提示
1 <= nums.length <= 5000-10^4 <= nums[i] <= 10^4nums中的每个值独一无二
解法
参考答案 (2 个标签)
二分查找 O(log n)
思路
旋转后数组分为两个有序部分。通过比较 nums[mid] 和 nums[left] 判断哪一半是有序的，然后判断 target 在哪一半。
代码实现
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
function search(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) return mid;
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}复杂度分析
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
图解
nums = [4, 5, 6, 7, 0, 1, 2], target = 0
第一次：left=0, right=6, mid=3
nums[mid]=7, nums[left]=4
左半边 [4,5,6,7] 有序
target=0 不在 [4,7) 中，搜索右半边
第二次：left=4, right=6, mid=5
nums[mid]=1, nums[left]=0
左半边 [0,1] 有序
target=0 在 [0,1) 中，搜索左半边
第三次：left=4, right=4, mid=4
nums[mid]=0 === target，返回 4