LeetCode 33. 搜索旋转排序数组

题目链接

33. 搜索旋转排序数组

题目思路

这个题比较容易的思路就是先寻找出数组分隔点,然后再通过target的大小进行二次二分查找。
但是其实我们可以把这两个步骤合二为一,但是要注意的坑比较多。
我们照常进行二分查找,如果nums[mid] == target,那就直接返回mid即可。
否则分以下的情况:

  1. 如果nums[mid] < nums[right],说明我们[mid, right]是有序的,我们需要进行深入的判断。
    i. 如果target < nums[mid],我们查找数组前半部分即可。
    ii. 如果target > nums[mid],我们需要再次判断:
    a. 如果target <= nums[right], 那么其肯定落在[mid, right]这个升序的区间中,我们left = mid + 1
    b. 如果target > nums[right], 那么target比当前有序部分的最大值还大,说明其不可能存在后半部分中,我们查询前半部分即可。
  2. 如果nums[mid] > nums[right],说明我们[left, mid]是有序的,同样也要深入判断。
    i. 如果target < nums[mid], 需要进行再次判断:
    a. 如果target <= nums[right], 那么它肯定落在数组的后半部分中,因为其比当前有序部分的最小值还要小。left = mid + 1
    b. 如果target > nums[right], 即 nums[right] < target < nums[mid],所以其应该落在我们的前半部分有序数组中。right = mid - 1
    ii. 如果target > nums[mid],直接查找数组有半部分即可。

因为题目说不存在重复元素,所以不需要判断nums[mid] == nums[right]的情况,否则我们需要进行right指针的偏移(这里就是搜索系列的第二题思路了)。

代码实现

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

总结

终于能吃透这类型的题目了,想通数组的内容就知道方法了。

原文地址:https://www.cnblogs.com/ZJPaang/p/13770451.html