网赌网站做流量渗透,网络营销推广招聘广告,vi设计公司专业品牌,网站关键词排名手机优化软件整数数组 nums 按升序排列#xff0c;数组中的值 互不相同 。
在传递给函数之前#xff0c;nums 在预先未知的某个下标 k#xff08;0 k nums.length#xff09;上进行了 旋转#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nums[1], …,…整数数组 nums 按升序排列数组中的值 互不相同 。
在传递给函数之前nums 在预先未知的某个下标 k0 k nums.length上进行了 旋转使数组变为 [nums[k], nums[k1], …, 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
提示
1 nums.length 5000 -104 nums[i] 104 nums 中的每个值都 独一无二 题目数据保证 nums 在预先未知的某个下标上进行了旋转 -104 target 104
var search function(nums, target) {var left 0,right nums.length-1// 特殊情况判断if(nums.length0){return -1}if(nums.length1){return nums[0]target?0:-1}// while(leftright)检查到了当target在左指针和右指针重合的位置如果是while(leftright)那么检查不到重合的位置while(leftright){var mid Math.floor((leftright)/2)if(nums[mid] target){return mid}else{// 中间的数字小于最右边的数字说明右边一定是有序的if(nums[mid]nums[right]){if(nums[mid]targettargetnums[right]){leftmid1}else{right mid-1}}else{// 右边是无序的左边是有序的if(nums[mid]targettargetnums[left]){right mid-1}else{left mid1}}}}return -1
};
