leetcode 153. Find Minimum in Rotated Sorted Array 、154. Find Minimum in Rotated Sorted Array II 、33. Search in Rotated Sorted Array 、81. Search in Rotated Sorted Array II 、704. Binary Search

这4个题都是针对旋转的排序数组。其中153、154是在旋转的排序数组中找最小值，33、81是在旋转的排序数组中找一个固定的值。且153和33都是没有重复数值的数组，154、81都是针对各自问题的版本1增加了有重复数值的限制条件。

153、154都需要考虑是否旋转成和原数组一样的情况，特别的，154题还需要考虑10111和11101这种特殊情况无法使用二分查找。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

33、81则不用考虑这些情况。

找最小值的题主要是利用最小值小于他前一个位置的数，同时也小于后一个位置的数

 

153. Find Minimum in Rotated Sorted Array 

class Solution {
public:
    int findMin(vector<int>& nums) {
        int start = 0;
        int end = nums.size() - 1;
        int mid;
        if(nums[start] < nums[end])
            return nums[start];
        while(start + 1 < end){
            mid = start + (end - start)/2;
            if(nums[mid] < nums[start])
                end = mid;
            else
                start = mid;
        }
        return nums[end];
    }
};

 

 

154. Find Minimum in Rotated Sorted Array II

class Solution {
public:
    int findMin(vector<int>& nums) {
        int start = 0;
        int end = nums.size() - 1;
        int mid = start + (end - start)/2;
        if(nums[start] < nums[end])
            return nums[start];
        if(nums[start] == nums[end] && nums[start] == nums[mid]){
            int min_num = INT_MAX;
            for(int i = 0;i < nums.size();i++){
                if(nums[i] < min_num)
                    min_num = nums[i];
            }
            return min_num;
        }
        while(start + 1 < end){
            mid = start + (end - start)/2;
            if(nums[mid] < nums[start])
                end = mid;
            else
                start = mid;
        }
        return nums[end];
    }
};

 

33. Search in Rotated Sorted Array

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

 

81. Search in Rotated Sorted Array II

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

http://www.cnblogs.com/grandyang/p/4325840.html

 

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄