C++利用二分法搜索旋轉陣列的旋轉點或目標值

看題：
題目很容易看明白，無非就是查找陣列最小值，而無論他旋轉多少次，其實都等于在固定點旋轉一次就可以實作輸入陣列，可以直接遍歷陣列查找最小值，但顯然這樣時間復雜度為O(N)，而我們采用二分法則會使得復雜度降到O(logN)

class Solution {
public:
    int findMin(vector<int>& nums) {
     int len=nums.size();
     if(!len||len==1)return nums[0];
     if(nums[0]<nums[len-1])return nums[0];//防止一開始就是一個有序陣列這樣進入下列回圈可能導致旋轉點判斷在陣列末尾
     int left=0,right=len-1;
     while(left<right){
         int mid=(left+right)/2;
         if(nums[0]<=nums[mid]){
              left=mid+1;        
         }
        else{
              right=mid;
         }
     }
     return nums[left];
    }
};

進一步應用，查找旋轉后的陣列中某一個目標值：
方法一：先找出旋轉點，在判斷目標值所在區間，然后在有序區間內查找目標值

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size(), mid = 0;
        while (left < right)
        {
            mid = (left + right) / 2;
            if (nums[0] > nums[mid])     right = mid;    //找出旋轉點
            else    left = mid + 1;
        }
        if (target < nums[0]) right = nums.size();      //判斷target在旋轉點左邊區間還是右邊區間
        else left = 0;
        while (left < right)
        {
            mid = (left + right) / 2;
            if (nums[mid] == target) return mid;         //繼續在有序的子區間找出目標下標
            else if (nums[mid] < target)  left = mid + 1;
            else if (nums[mid] > target)  right = mid;
        }
        return -1;
    }
};

方法二：將陣列一分為二，其中一定有一個是有序的，另一個可能是有序，也能是部分有序，
此時有序部分用二分法查找，無序部分再一分為二，其中一個一定有序，另一個可能有序，可能無序，就這樣回圈.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;
        int p1 = 0, p2 = nums.size() - 1;
        int mid = p1;
        while (p1 <= p2)
        {
            mid = (p1 + p2) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] >= nums[p1]) // 說明[p1,mid]區間是有序的
            {
                // 因為[p1,mid]區間是有序的，所以通過p1和mid處的值就能判斷target在不在區間內
                if (nums[p1] <= target && target < nums[mid]) p2 = mid - 1;
                else p1 = mid + 1; // 如果不在，就去[mid+1,p2]區間找target
            }
            else // 說明[mid,p2]區間是有序的
            {
                // 因為[mid,p2]區間是有序的，所以通過mid和p2處的值就能判斷target在不在區間內
                if (nums[mid] < target && target <= nums[p2]) p1 = mid + 1;
                else p2 = mid - 1; // 如果不在，就去[p1,mid-1]區間找target
            }
        }
        return -1;
    }
};

進階：查找含有重復元素的陣列時，我們會遇到一種情況：
nums[left] = nums[mid] 和nums[mid] = nums[right]，同時成立，例如：旋轉后陣列為[1,0,1,1,1]此時沒辦法判斷那個區間有序，那個區間無序，所以此時要使得left++，right–，區間縮小在進行判斷

class Solution {
public:
    bool search(vector<int>& nums, int target) {//有重復元素時

        int len = nums.size();
        if (!len)return false;
        int left = 0, right = len - 1;
        while (left <= right) {
            int mid = (right + left) / 2;
            if (target == nums[mid])return true;
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                left++;
                right--;
            }
            else if (nums[left] <= nums[mid]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                }
                else {
                    left = mid + 1;
                }
            }
            else {
                if (target <= nums[right] && target > nums[mid]) {
                    left = mid + 1;
                }
                else {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
};