鹅厂员工在内部圈吐槽:研发中心有好几位组长压根不会写代码，那技术组长的核心竞争力到底是啥?

昨天晚上十一点多回家，电梯口等了半天，手里拎着外卖，脑子里还在想一个小问题。就是那个…“旋转数组最小值”。你们肯定见过吧？一个原本升序的数组，被从某个位置掰开接到前面，比如 [1,2,3,4,5] 变成 [3,4,5,1,2]，要你找最小那个数。看着简单，手一抖就会写成线性扫描，但总觉得不甘心，对吧。

我在公司楼下抽烟的时候，想了下直觉：如果没有旋转，最小值就是第一个；有旋转的话，最小值落在“断点”处。于是自然而然想到二分。可是…别急，坑在于重复元素。没有重复时，比较 nums[mid] 和 nums[right] 就能判断哪边有序；有重复时，可能相等导致方向不明确，只能把右边界往左缩一下“去重”，不然会卡住。对了，空数组要提前拦截，不然面试官会皱眉。

二分的核心判断就三句：

1. nums[mid] > nums[right]：最小值在右半边，left = mid + 1。
2. nums[mid] < nums[right]：最小值在左半边（含 mid），right = mid。
3. nums[mid] == nums[right]：方向不明，right--，丢掉一个重复尾巴，保证不会错过最小值。

为啥比较的是 right 不是 left？因为右端在被旋转后，往往跨过“断点”，信息量更足；而且用 right 能自然地把“最小值收缩到左侧”这件事表达清楚。时间复杂度平均是 O(log n)，但一旦重复特别多，最坏会退化到 O(n)，这点别和面试官硬刚，认了就行。

publicclassRotatedArrayMin{
publicstaticintfindMin(int[] nums){
if (nums == null || nums.length == 0) {
thrownew IllegalArgumentException("数组不能为空");
        }
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
// 断点在右边
                left = mid + 1;
            } elseif (nums[mid] < nums[right]) {
// 最小值在左边（含mid）
                right = mid;
            } else {
// nums[mid] == nums[right]，无法判断，收缩右侧
                right--;
            }
        }
return nums[left];
    }

// 如果题目明确“无重复”，可以用更干脆的版本
publicstaticintfindMinNoDup(int[] nums){
if (nums == null || nums.length == 0) {
thrownew IllegalArgumentException("数组不能为空");
        }
int l = 0, r = nums.length - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (nums[m] > nums[r]) l = m + 1;
else r = m;
        }
return nums[l];
    }
}

有人会问：完全没旋转呢？比如 [1,2,3]。上面代码没问题，比较关系会把 right 慢慢推到最小处，也就是最左边。还有一个边界是全相等 [2,2,2]，那就只能靠 right-- 慢慢缩，确实会退化，但结果对。嗯…我现在有点困，不过这个套路你们记住就行：右端作参照，三分支判断，遇到相等就右缩一格。