Find Minimum in Rotated Sorted Array

153. Find Minimum in Rotated Sorted Array

Suppose a sorted array 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). Find the minimum element. You may assume no duplicate exists in the array.

S: binary search 如果某个子段首元素小于末元素，则该子段里没有pivot

int findMin(vector<int>& nums) {
    int size = nums.size();
    int l = 0, r = size-1;
    while(l+1 < r && nums[l] > nums[r]){
        int mid = l + (r-l)/2;
        if(nums[l] < nums[mid]) l = mid;
        else r = mid;
    }
    return min(nums[l], nums[r]);
}

154. Find Minimum in Rotated Sorted Array II

Follow up for "Find Minimum in Rotated Sorted Array": What if duplicates are allowed? Would this affect the run-time complexity? How and why?

Suppose a sorted array 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).

Find the minimum element. The array may contain duplicates.

S: bianry search

worst case O(n)

    int findMin(vector<int>& nums) {
        int start = 0, end = nums.size()-1;
        while(start+1 < end && nums[start] >= nums[end]){
            int mid = start + (end - start)/2;
            if(nums[start] < nums[mid]) start = mid;
            else if(nums[start] > nums[mid]) end = mid;
            else start++;//相等时只能缩减一位，而不是去掉一半
        }
        return min(nums[start], nums[end]);
    }

33. Search in Rotated Sorted Array

Suppose a sorted array 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).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

S： binary search O（logn）

无论如何至少有一半元素是排好序的，从排好序的那一半入手

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

1. Search in Rotated Sorted Array II Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

S：binary search O(logn) worst case: O(n)

和没有duplicate唯一的区别是相等的时候只能缩进一步，二分不work，直接for loop

    bool search(vector<int>& nums, int target) {
        int size = nums.size();
        int start = 0, end = size-1;
        while(start+1 < end){
            int mid = start + (end-start)/2;
            if(nums[start] == nums[mid]) start++;//相等只能缩进一步
            else if(nums[start] < nums[mid]){
                if(nums[start] <= target && nums[mid] >= target) end = mid;
                else start = mid;
            }
            else if(nums[start] > nums[mid]){
                if(nums[mid] <= target && nums[end] >= target) start = mid;
                else end = mid;
            }
        }
        if(nums[start] == target) return true;
        if(nums[end] == target) return true;
        return false; 
    }