本文主要是介绍leetcod题:33. 搜索旋转排序数组(中等),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、题目描述:33. 搜索旋转排序数组(中等)
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -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来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、题解分析
使用二分法分为几种情况,left、right 分别代表左右下标
1、(nums[left] < nums[right] && nums[mid] < target) ,left = mid +1;
2、(nums[left] < nums[right] && nums[mid] > target) ,left = mid-1;
3、(nums[left] > nums[right]) && target<nums[right] && target < nums[mid] && nums[mid] < nums[right] ,right= mid -1;
4、(nums[left] > nums[right]) && target<nums[right] && target < nums[mid] && nums[mid] > nums[right], left = mid +1;
5、(nums[left] > nums[right]) && target>nums[right] && target < nums[mid] , right= mid -1;
6、(nums[left] > nums[right]) && target>nums[right] && target > nums[mid] && nums[mid] > nums[right], left = mid +1;
7、(nums[left] > nums[right]) && target>nums[right] && target > nums[mid] && nums[mid] < nums[right], right= mid -1;
三、代码
class Solution {
public:int search(vector<int>& nums, int target) {int mid = 0;int head = 0,tail = nums.size()-1;while(head < tail){mid = (head + tail)/2;if(nums[mid] == target)return mid;if(nums[head] == target)return head;if(nums[tail] == target)return tail;if(head + 1 == tail){if(nums[head] == target){return head;}else if(nums[tail] == target){return tail;}else{return -1;}}if(nums[head] > nums[tail]){if(target<nums[tail] ){if(nums[mid] < nums[tail] ){if(nums[mid] < target){head = mid;//continue}else{tail =mid;}}else{head = mid;}}else{if(nums[mid] < nums[tail]){tail = mid;}else{if(nums[mid] < target){head = mid;}else{tail = mid;}}}}else{if(nums[mid] < target){head = mid;}else{tail =mid;}}}if(tail == head && nums[head] == target)return mid;else{return -1;}}
};
这篇关于leetcod题:33. 搜索旋转排序数组(中等)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!