网站开发入门教程,官网网站备案,二维码生成器app,上传照片的网站赚钱33. 搜索旋转排序数组。
整数数组 nums 按升序排列#xff0c;数组中的值 互不相同 。
在传递给函数之前#xff0c;nums 在预先未知的某个下标 k#xff08;0 k nums.length#xff09;上进行了 旋转#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1…33. 搜索旋转排序数组。
整数数组 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
-10^4 nums[i] 10^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 target 10^4算法分析
解题思路
先二分找到nums[0]的位置targetnums[0], 继续二分左部分 否则二分右部分二分结束判断二分值是否等于target等于返回否则返回-1
class Solution {public int search(int[] nums, int target) {if (nums.length 0) return -1;int l 0, r nums.length - 1;while (l r) {int mid l r 1 1;if (nums[mid] nums[0]) l mid;else r mid - 1;}if (target nums[0]) {l 0;} else {l r 1;r nums.length - 1;}while (l r) {int mid l r 1;if (nums[mid] target) r mid;else l mid 1;}if (nums[r] target) return r;return -1;}
}复杂性分析
时间复杂度O(n) 空间复杂度O(1)
