搜索旋转数组II[抽象二分练习]

前言

抽象二分，常见考题，以二分快速逼近的思想，抽象判断规则，实现低时间复杂度寻找target。

一、搜索旋转数组II

二、抽象二分

package everyday.medium;

// 搜索旋转排序数组II
public class Search {
    
    /* target：一个升序数组，从下表k开始旋转得到新数组，即两个有序子数组。 所以，可以先快速找到k在那里，然后两次二分，确定target是否存在。 二分如何确定k?其实就算考察抽象二分，判断规则抽象。 定义为，midVal > nums[0]，说明mid在第一个子数组，则low = mid; midVal < nums[0],说明mid进入第二个子数组中，则high = mid - 1 如果两者相等，这个值可能属于第一数组，也可能属于第二个数组。这是一个问题，无法判断。 [2,2,2,2,2,2,2,0,1,2] | [2,2,2,0,1,2,2,2,2,2,2] 破局？当左中右相等时,则不急着取mid，而是右边向左走一格，这样左边的值是回小于等于nums[high]的。 最终取到第一个数组的尾巴 i，则i+1就算最小值所在。 */
    public boolean search(int[] nums, int target) {
    
        // 二分寻k,抽象二分。
        int low = 0, high = nums.length - 1;
        // 二分快速找到比nums[0]小的，第一个小的。
        int first = nums[0];
        while (low < high) {
    
            int mid = low + (high - low + 1 >>> 1);
            int midVal = nums[mid];

            if (midVal > first) low = mid;
            else if (midVal < first) high = mid - 1;
            else if (midVal == nums[high]) high--;//往左走一步，走边是较小的值
                // 可合并。
            else low = mid;
        }

        return binarySearch(nums, 0, low, target)
                || binarySearch(nums, low + 1, nums.length - 1, target);
    }

    // 二分查找target。
    private boolean binarySearch(int[] nums, int low, int high, int target) {
    
        while (low <= high) {
    
            int mid = low + (high - low >>> 1);
            int midVal = nums[mid];

            if (midVal == target) return true;
            if (midVal < target) low = mid + 1;
            else high = mid - 1;
        }
        return false;
    }

    public static void main(String[] args) {
    
        new Search().search(new int[]{
    2, 2, 2, 3, 2, 2, 2}, 2);
    }
}

注：官方的答案，是一次抽象二分就搞定了，我这里写复杂了，纯当练习。

总结

1）抽象二分练习

参考文献

[1] LeetCode 搜索旋转数组II