题目链接

注意点

题目给的序列是一个有序数组按某个轴旋转后的数组

要求时间复杂度为O(logn)

解法

解法一：根据题目的时间复杂度O(logn)要求，很容易想到要用二分搜索。但是二分搜索要求数组是有序的，这样才能判断target在左半边还是右半边，题目的数组并不是整个都是有序的。根据nums的特点可以发现要么[left,mid]是有序的要么[mid,right]是有序的。如果nums[left] < nums[mid]成立可以说明[left,mid]有序，反之[mid,right]有序。在确定了哪半边有序之后就可以用两端端点判断target是否在区间内，进而确定接下来搜索左半边或是右半边。

class Solution {public:    int search(vector
    
     & nums, int target) {        int low = 0,high = nums.size()-1;        while(low <= high)        {            int mid = low + (high-low)/2;            if(nums[mid] == target) return mid;            if(nums[low] <= nums[mid])            {                if(target >= nums[low] && target <= nums[mid]) high = mid-1;                else low = mid+1;            }            else            {                if(target >= nums[mid] && target <= nums[high]) low = mid+1;                else high = mid-1;            }        }        return -1;    }};

小结

变种题Search in Rotated Sorted Array - LeetCode

转载于:https://www.cnblogs.com/multhree/p/10387646.html

你可能感兴趣的文章