力扣LeetCode33（Java）:搜索旋转排序数组

题目描述

题目分析

本题目要求设计出一个时间复杂度为 O(log n) 的算法解决此问题，果断采用二分。但是这道题目它不是全部排好顺序的，而是两个有序的拼成一个数组，因此这样在计算出mid不等于target的时候，就需要具体情况具体分析，我们将它分成两种情况进行分析。

• 情况1：nums[0]<=nums[mid]
• 情况2：nums[0]>nums[mid]

为什么这样分呢？因为我们需要抓住target一定存在的区间来确定left或者right的值。
对于情况1nums[0]<=nums[mid]，在这种情况下，如果nums[0]<=target&&target<nums[mid]，这就说明target一定存在于[0,mid）这个区间，因此我们使right = mid-1，让二分查找的区间向左逼近，其余情况则在（mid,nums.length-1]这个区间。
对于情况2nums[0]>nums[mid]，在这种情况下，如果nums[mid]<target&&target<=nums[nums.length-1]，这就说明target一定存在于（mid,nums.length-1]，因此我们使left = mid + 1，让二分查找的区间向右逼近，其余情况则在[0,mid）这个区间。

代码

class Solution {
    public int search(int[] nums, int target) {
        int left = 0,right = nums.length-1;
        while(left<=right){
            int mid = left + (right-left)/2;
            if(nums[mid]==target){
                return mid;
            }
            if(nums[0]<=nums[mid]){
                if(nums[0]<=target&&target<nums[mid]){
                    right = mid-1;
                }else{
                    left = mid +1;
                }
            }else{
                if(nums[mid]<target&&target<=nums[nums.length-1]){
                    left = mid + 1;
                }else{
                    right = mid-1;
                }
            }
        }
        return -1;
    }
}