Leetcode|区间首尾元素大小判断成序+二分查找|33. 搜索旋转排序数组

SL_World

发布于 2022-01-10 15:14:54

2680

发布于 2022-01-10 15:14:54

文章被收录于专栏：XX

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;
    }
};