首页 > 代码库 > 81. Search in Rotated Sorted Array II
81. Search in Rotated Sorted Array II
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7
might become 4 5 6 7 0 1 2
).
Write a function to determine if a given target is in the array.
The array may contain duplicates.
解题思路:给定的数组可能是循环右移过的,也可能是排序好没动过的。每次依然按照原来的二分查找,不过这里的二分查找只能知道左右的一部分是排序好的,另外一部分还是可能分段有序的。
首先取得nums[mid]处的值,如果nums[mid]>nums[high]则可以断定左半段是有序的,此时看target是否属于区间[nums[low],nums[mid]]之间,如果是的话直接将high置为mid-1,否则targe>nums[mid]或者target<nums[low],显然无论哪种情况都不会出现在左半部分了,所以需要继续判断右半段。例如 target=1,而现在的序列为345678123,此时nums[mid]=7。同理可求当nums[mid]<nums[high]时的指针移动方向。
本题最烦的应该就是可以有重复值了,当mid和hi相同时,无法确定哪半段是有序的。如 1 1 1 1 2 1和 1 2 1 1 1 1两种情况都是可能存在的,所以可以将high指针往左移动一位,直到不想等为止。另外如果把mid和low比较也是可以的。
class Solution { public: bool search(vector<int>& nums, int target) { int low=0,high=nums.size()-1; while(low<=high){ int mid=low+((high-low)>>1); if(nums[mid]==target)return true; if(nums[mid]<nums[high]){ if(nums[mid]<target&&target<=nums[high])low=mid+1; else high=mid-1; } else if(nums[mid]>nums[high]){ if(nums[low]<=target&&target<nums[mid])high=mid-1; else low=mid+1; } else high--; } return false; } };
81. Search in Rotated Sorted Array II