YSMull
<-- algorithm



原题链接

题目描述

一个升序数组,被切了一刀,分为两个部分,这两部分交换位置从新组合在一起,搜索旋转排序数组中的某个数字

方法一

分析

这题考察分类讨论的能力,首先我们画出这个数组的结构:

对该数组进行二分查找时,一定可以判断出 mid 的值处于「上」还是「下」,这样我们可以对 mid 进行分类讨论:

  1. 如果 mid 落在「上」:
    如果 target 也落在「上」且小于 mid,那么 target 在左半边,否则 target 在右半边
  2. 如果 mid 落在「下」:
    如果 target 也落在「下」且大于 mid,那么 target 在右半边,否则 target 在左半边

这里为什么是对 mid 进行分类讨论,而不是对 target 进行分类讨论呢? 原因在于,当我们求出 mid 的值的时候, 就已经可,以确定 mid 处于「上」还是「下」了,而 target 仍然处于 「上」、「下」叠加态。 同样的,我们也不会对「拐点」进行分类讨论,因为我们根本都还不知道拐点在哪里。

分类讨论的时候,如果不知道怎么讨论,最好先对已经可以确定的量去讨论

实现

class Solution {
    public int search(int[] nums, int target) {
        return search(nums, target, 0, nums.length - 1);
    }

    public int search(int[] nums, int target, int i, int j) {
        if (i > j) return -1;
        int idx = (i + j) / 2;
        int l = nums[i], r = nums[j], n = nums[idx];
        if (target == n) return idx;
        if (target == l) return i;
        if (target == r) return j;
        // 因为此时 n 的位置已经可以确定了,所以先讨论 n 的位置
        if (n > r) { // 如果 n 在上
            if (l < target && target < n) { // target 也在上,并且小于 n
                return search(nums, target, i + 1, idx - 1);
            } else {
                return search(nums, target, idx + 1, j - 1);
            }
        } else { // 如果 n 在下
            if (n < target && target < r) { // target 也在下,并且大于 n
                return search(nums, target, idx + 1, j - 1);
            } else {
                return search(nums, target, i + 1, idx - 1);
            }
        }
    }
}

方法二

分析

使用 模板法,由于 check 函数也需要引入 [l, r),参数,直接使用 r 会越界,因此先不搜索数组的最后一个元素,只考察[0, len - 2] 范围内的子数组,如果没有搜索到,此时 l 会位于 len-1 处。

实现

class Solution {
    boolean check(int l, int r, int mid, int[] nums, int target) {
        if (nums[l] <= nums[r]) { // 已经在递增区间了
            return nums[mid] >= target;
        } else {// 区间仍然是旋转数组,mid 和 target 的位置有六种情况,其中三种符合条件
            if (nums[l] <= target && target <= nums[mid]) return true;
            if (target <= nums[mid] && nums[mid] <= nums[r]) return true;
            if (nums[mid] <= nums[r] && nums[l] <= target) return true;
            return false;
        }
    }
    public int search(int[] nums, int target) {
        // 只搜索除了最后一个元素以外的位置
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l ) / 2;
            if (check(l, r, mid, nums, target)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        // 如果没有满足条件的, l 指向最后一个位置
        // 如果有满足条件的,l 也可能没有取等
        if (nums[l] != target) return -1;
        return l;
    }
}