文章目录
- 搜索旋转排序数组
- 我的思路
- 网上思路
- 总结
搜索旋转排序数组
整数数组 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 。
示例 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
我的思路
使用 findIndex
网上思路
二分法
我的思路
var search = function (nums, target) {return nums.findIndex(item => item === target)
};
讲解
普通的一个方法
网上思路
var search = function (nums, target) {let left = 0;let right = nums.length - 1;// 找到旋转点while (left < right) {const mid = Math.floor((left + right) / 2);if (nums[mid] > nums[right]) {left = mid + 1; // 旋转点在右半部分} else {right = mid; // 旋转点在左半部分}}const rotationIndex = left; // 旋转点的下标// 根据目标值与旋转点的关系确定搜索区间left = 0;right = nums.length - 1;if (target >= nums[rotationIndex] && target <= nums[right]) {left = rotationIndex; // 在右半部分} else {right = rotationIndex - 1; // 在左半部分}// 在确定的区间内执行标准二分搜索while (left <= right) {const mid = Math.floor((left + right) / 2);if (nums[mid] === target) {return mid; // 找到目标值,返回下标} else if (nums[mid] < target) {left = mid + 1; // 在右半部分} else {right = mid - 1; // 在左半部分}}return -1; // 未找到目标值
}
讲解
- 找到旋转点
旋转点是数组中最小元素的索引。我们可以使用二分搜索来找到这个点:
初始化 left 为 0,right 为数组的最后一个索引。
进行循环,直到 left 小于 right:
计算中间索引 mid。
如果 nums[mid] 大于 nums[right],说明旋转点在右半部分,因此更新 left = mid + 1。
否则,旋转点在左半部分,更新 right = mid。
最终,left 将指向旋转点的索引。- 确定搜索区间
根据 target 的值与旋转点的关系,决定在哪一部分进行搜索:
如果 target 在旋转点到数组末尾的范围内(即 nums[rotationIndex] <= target <= nums[right]),则在右半部分搜索。
否则,在左半部分搜索。- 执行标准二分搜索
在确定的区间内进行标准的二分搜索:
初始化 left 和 right 指向确定的搜索区间。
进行循环,直到 left 小于等于 right:
计算中间索引 mid。
如果 nums[mid] 等于 target,返回 mid。
如果 nums[mid] 小于 target,则 target 在右半部分,更新 left = mid + 1。
否则,target 在左半部分,更新 right = mid - 1。
如果循环结束后仍未找到 target,返回 -1。
总结
不知不觉已经坚持了40天了,加油