Leetcode|區間首尾元素大小判斷成序+二分查找|33. 搜尋旋轉排序數組

1 旋轉數組的二分查找

• 在二分搜尋基礎上，判斷左右區間中的收尾元素大小，來判斷是否成序，不成序或target在這個區間則搜尋，否則搜尋另外一個區間

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int size = nums.size();
        int left = 0, right = size - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (target == nums[mid]) 
                return mid;
            else if (target < nums[mid]) {
                // 左側不成序列 || 左側升序 且 target ＞= 左側最小值，則說明target可能在左側區間中，否則在右區間尋找
                if (nums[left] > nums[mid] || (nums[left] < nums[mid] && target >= nums[left]))
                    right = mid - 1;
                else left = mid + 1;
            } else if (target > nums[mid]) {
                if (nums[mid] > nums[right] || (nums[mid] < nums[right] && target <= nums[right]))
                    left = mid + 1;
                else right = mid - 1;
            }
        }
        return -1;
    }
};           

複制