[leetcode] 153/33 Search / Find

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]).
Find the minimum element.
You may assume no duplicate exists in the array.
Example 1:
Input: [3,4,5,1,2]
Output: 1
Example 2:
Input: [4,5,6,7,0,1,2]
Output: 0

找到 旋转有序数组中的最小值

排序数组找数，根据排序数组的性质，自然会想到二分查找。
通过题意， 我们知道 这是 2段(a...b , c...d) 排序数组拼在一起，
并且满足旋转的性质 c< d < a < b

那方法就是 依然采用 二分查找的办法 ， 找出 b点 和c 点.

1. 当 mid 点 大于 d， 说明 mid 点的位置 在a... b 之间
   类似 a...mid...b...c ....d , 那么我们继续查找 mid...b...c ....d

2 .当 mid 点 小于 d， 说明 mid 点的位置 在c... d 之间
类似 a....b...c ..mid..d , 那么我们继续查找 a....b...c ..mid

3. mid 等于end 或者 推出循环，就表示 查找范围已经缩小到 [c,d]了

image.png

其次就是，mid 比较的时候 ，要跟 end比 ，因为 会有 a..d 为空的情况，类似
[1,2,3] -- > 1 当然这种情况你可以直接输出...

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

image.png

查找旋转有序数组

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]).
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.
Your algorithm's runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

这题就是在上题的基础上， 多了一步查找target
就是 用2次二分查找

1. 找到 旋转数字的最小值的下标 pivot
2. 在对应的区间内二分查找 target

这里要处理旋转数组的特殊情况， 就是自身就是一个有序数组。

1. 如果自身就是有序数组， 那么直接二分查找[0: nums.size()-1]
2. 根据target 来确定 二分[0: pivot-1] 或者 [pivot : nuns.size()-1]

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

        pivot = end;

        if(flag) {begin = 0; end = nums.size()-1;}
        else if(target >= nums[0]) {begin =0; end =pivot-1 ; }
        else {begin = pivot; end = nums.size()-1 ;}
        
        while(begin +1 < end){
            mid = begin + (end - begin)/2;
            if (nums[mid] > target) end = mid;
            else if(nums[mid] < target) begin = mid;
            else return mid;
        }
        
        if(nums[begin] == target) return begin;
        else if(nums[end] == target) return end;
        else return -1;
        
    }
};

image.png