原题地址：搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 $O(logn)$ 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
二分查找
题目要求时间复杂度为$O(logn)$，显然要求使用二分查找算法。因为数组原来是有序的，只是进行了一次旋转，所以我们使用二分查找时，始终会有一半是有序的，如果我们要找的target不在这一半有序的数据这内，我们再继续二分查找另一半数据即可。
具体实现代码如下：
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
const search1 = function(nums, target) {
// 二分查找区间的左右端点和中间的序号
let [left, right, middle] = [0, nums.length - 1, Math.floor(nums.length / 2)];
while (left <= right) {
if (nums[middle] === target) { // 已经找到了
return middle;
}
if (nums[left] < nums[right]) { // 已经有序，正常二分搜索即可
if (nums[middle] < target) {
[left, middle] = [middle + 1, Math.floor((middle + right + 1) / 2)];
} else {
[right, middle] = [middle - 1, Math.floor((left + middle - 1) / 2)]
}
} else {
if (nums[middle] > nums[right]) { // 左半部分是正序的
if (nums[middle] >= target && nums[left] <= target) {
[right, middle] = [middle - 1, Math.floor((left + middle - 1) / 2)]
} else {
[left, middle] = [middle + 1, Math.floor((middle + right + 1) / 2)];
}
} else {
if (nums[middle] <= target && nums[right] >= target) {
[left, middle] = [middle + 1, Math.floor((middle + right + 1) / 2)];
} else {
[right, middle] = [middle - 1, Math.floor((left + middle - 1) / 2)]
}
}
}
}
return -1;
};
测试：
let start = new Date();
const test = search1;
console.log(test([4,5,6,7,0,1,2], 0)); // 4
console.log(test([4,5,6,7,0,1,2], 3)); // -1
console.log(test([3,5,1], 3)); // 0
console.log(new Date().getTime() - start.getTime()); // 8
时间复杂度： 二分查找，时间复杂度为$O(logn)$
空间复杂度： 空间复杂度为$O(1)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 3,2019