带反复元素的二分查找

例题：旋转数组的最小数字

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…

例题

把一个数组最开始的若干个元素搬到数组的开端，咱们称之为数组的旋转。输出一个递增排序的数组的一个旋转，输入旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为 1。

示例

示例 1：

 输出：[3,4,5,1,2]
输入：1

示例 2：

 输出：[2,2,2,0,1]
输入：0

题解

高兴的一天从力扣的每日一题开始。发现明天难度是 easy，于是决定做进去再去吃早饭。

点开题目一看，这不是爆搜吗 hhhh。但咱们是有幻想有谋求的人，这么简略的题目怎么能忍耐工夫复杂度为 O(n) 的搜寻。于是我将二分查找的板子砸了下来：

public class Solution {public int minArray(int[] numbers) {
        int len = numbers.length;
        int l = 0, r = len-1;
        int ans;
        while (l <= r) {int mid = l + ((r-l) >> 1);
            if (numbers[mid] > numbers[l]) {l = mid + 1;} else if (numbers[mid] < numbers[l]) {r = mid - 1;} else {ans = numbers[mid];
                break;
            }
        }
        return ans;
    }
}

而后：

起初依据谬误的案例才反馈过去，这个有序数组是蕴含反复元素的。在二分过程中，还须要退出去重这一步骤。

这里套用官网了解的一张图进行阐明：

在理论比拟过程中，对反复元素的二分是没有意义的。如上图，最大索引和最小索引的平均值代表的索引，他们的值可能齐全一样，所以须要去重操作，使得被二分的索引不会和最大值雷同。代码如下：

class Solution {public int minArray(int[] numbers) {
        int len = numbers.length;
        int l = 0, r = len-1;
        while (l < r) {int mid = l + ((r-l) >> 1);
            if (numbers[mid] > numbers[r]) {l = mid + 1;} else if (numbers[mid] < numbers[r]) {r = mid;} else {
                // 最大值与最小值雷同，或者曾经找到了最小值两种可能
                // 如果是因为反复元素，就通过 r -- 实现去重
                // 如果是因为曾经找到了最小值, 即 mid = l = r-1; 这是 r -- 之后，l<r，不再满足循环条件，退出循环.
                r--;
            }
        }
        return numbers[l];
    }
}

总结

对于容许反复元素的有序数组，能够通过有去重操作的二分查找来搜寻。这也算是一道模板题，在此留作笔记待日后温习。

对于工夫复杂度：与反复元素的多少无关，当没有反复元素时，工夫复杂度为 O(log(n))；当数组全副是反复元素时，工夫复杂度为 O(n)