难度:中等
整数数组 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 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 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
双指针法
思路
要求时间复杂度O(log n)首先想到二分法,但二分法适用于有序数组,本题中的数组可以理解为:由两个升序数组拼接而成的数组,但第一个升序数组的最小值是大于第二个升序数组的最大值的。
已知在数组中取最中间的数:
- 这个数等于target,则直接返回
- 不等于,再判断:
2.1. 这个数大于最后一个数的值,则这个数的左侧部分是有序的
2.2.小于,则右侧部分是有序的
分别在有序部分中判断target是否在这个区间,在则继续缩小区间,不在则在另一侧区间
var search = function(nums, target) {var start = 0var end = nums.length - 1var middle while(start<=end){middle = Math.floor((start+end)/2) //向下取整if(nums[middle] == target){ //如果中间值正好是target,则直接返回return middle}//如果不是,则判断//1、中间值小于右指针的值,则右侧区间(middle,end]有序//2、中间值大于右指针的值,左侧区间[start,middle)有序if(nums[middle]<nums[end]){ if(nums[middle]<target && target<=nums[end]){//在(middle,end]区间start = middle+1}else{ //在[start,middle)end = middle - 1}}else{ if(nums[start]<=target && target<nums[middle]){//在[start,middle)区间end = middle-1}else{ //在(middle,end]区间start = middle+1}}}return -1
};