Leetcode 33 -- 二分查找&&归约思想

题目描述

搜索旋转排序数组

思路

思路来源
一个清晰的思路：这道题和平常二分法查找的不同就在于,把一个有序递增的数组分成了,两个递增的数组,我们需要做的就是判断这个数在哪一个递增的数组中,然后再去用常规的二分法去解决

代码1

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[0] <= nums[mid] && nums[0] <= target && target <= nums[mid])
            {
                r = mid;
            }
            else if(nums[mid] < nums[0] && target <= nums[mid])
            {
                r = mid;
            }
            else if(nums[mid] < nums[0] && nums[0] <= target)
            {
                r = mid;
            }
            else 
            {
                l = mid + 1;
            }
        }
        return nums[l] == target ? l : -1;
    }
};

位运算优化版

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
            {
                l = mid + 1;
            }
            else 
            {
                r = mid;
            }
        }
        return nums[l] == target ? l : -1;
    }
};