33.搜索旋转排序数组
题目来源:
leetcode题目,网址:33. 搜索旋转排序数组 - 力扣(LeetCode)
解题思路:
在二分查找时,分情况讨论即可。通过与第一个元素和最后一个元素的比较来获得 mid 处于第一个序列中还是第二个序列中。
解题代码:
class Solution {
public:int search(vector<int>& nums, int target) {if(target==nums[0]){return 0;}else if(target==nums[nums.size()-1]){return nums.size()-1;}int left=1;int right=nums.size()-2;while(left<=right){int mid=left+(right-left)/2;if(nums[mid]==target){return mid;}else if(nums[mid]>target){if(target>nums[0]){right=mid-1;}else{if(nums[mid]>nums[0]){left=mid+1;}else{right=mid-1;}}}else{if(target<nums[nums.size()-1]){left=mid+1;}else{if(nums[mid]<nums[nums.size()-1]){right=mid-1;}else{left=mid+1;}}}}return -1;}
};
总结:
官方题解也是二分,不过他是先判断[l,mid] 和 [r,mid] 哪个有序,若不在有序的区间中,则在无序的区间中。