算法编程题：二分查找（6 题）

解题思路： 维护可能包含目标的闭区间，比较中点后排除一半。

不变量： 若目标存在，则始终位于闭区间 [left,right] 中。

public static class AlgCode047Solution
{
    public static int Solve(int[] numbers, int target)
    {
        int left = 0, right = numbers.Length - 1;
        while (left <= right)
        {
            int middle = left + (right - left) / 2;
            if (numbers[middle] == target) return middle;
            if (numbers[middle] < target) left = middle + 1;
            else right = middle - 1;
        }
        return -1;
    }
}

复杂度： 时间 O(log n)，额外空间 O(1)。

边界用例： 空数组；单元素；目标不存在；重复值返回任意位置。

面试追问：

• 如何修改为返回第一个等于目标值的位置？

解题思路： 在半开区间中，满足 >= target 时保留中点并收缩右边界。

不变量： left 左侧全部小于目标，right 及其右侧不属于未决区间。

public static class AlgCode048Solution
{
    public static int Solve(int[] numbers, int target)
    {
        int left = 0, right = numbers.Length;
        while (left < right)
        {
            int middle = left + (right - left) / 2;
            if (numbers[middle] < target) left = middle + 1;
            else right = middle;
        }
        return left;
    }
}

复杂度： 时间 O(log n)，额外空间 O(1)。

边界用例： 空数组；目标小于全部值；目标大于全部值；重复值。

面试追问：

• 如何由下界实现有序数组的插入位置？

解题思路： 分别计算第一个 >= target 与第一个 > target 的位置。

不变量： 两个边界函数分别维护各自的真假分界。

public static class AlgCode049Solution
{
    public static int[] Solve(int[] numbers, int target)
    {
        int first = Bound(numbers, target, strict: false);
        if (first == numbers.Length || numbers[first] != target) return [-1, -1];
        int after = Bound(numbers, target, strict: true);
        return [first, after - 1];
    }
    
    private static int Bound(int[] numbers, int target, bool strict)
    {
        int left = 0, right = numbers.Length;
        while (left < right)
        {
            int middle = left + (right - left) / 2;
            bool moveRight = strict
                ? numbers[middle] <= target
                : numbers[middle] < target;
            if (moveRight) left = middle + 1;
            else right = middle;
        }
        return left;
    }
}

复杂度： 两次二分，总时间 O(log n)，额外空间 O(1)。

边界用例： 空数组；目标不存在；全部值相等；目标位于两端。

面试追问：

• 如何用标准库 BinarySearch 的返回值推导插入点？

解题思路： 每轮至少有一半有序，根据目标是否位于该半段决定保留范围。

不变量： 如果目标存在，它始终位于当前闭区间。

public static class AlgCode050Solution
{
    public static int Solve(int[] numbers, int target)
    {
        int left = 0, right = numbers.Length - 1;
        while (left <= right)
        {
            int middle = left + (right - left) / 2;
            if (numbers[middle] == target) return middle;
            if (numbers[left] <= numbers[middle])
            {
                if (numbers[left] <= target && target < numbers[middle])
                    right = middle - 1;
                else
                    left = middle + 1;
            }
            else
            {
                if (numbers[middle] < target && target <= numbers[right])
                    left = middle + 1;
                else
                    right = middle - 1;
            }
        }
        return -1;
    }
}

复杂度： 时间 O(log n)，额外空间 O(1)。

边界用例： 空数组；未旋转；单元素；目标不存在。

面试追问：

• 允许重复值后为什么最坏复杂度可能退化为 O(n)？

解题思路： 速率越大所需时间越少，对最小可行速率做答案二分。

不变量： 小于 left 的速率已证不可行，大于等于 right 的候选保留可行边界。

public static class AlgCode051Solution
{
    public static int Solve(int[] workloads, int hours)
    {
        int left = 1, right = workloads.Max();
        while (left < right)
        {
            int rate = left + (right - left) / 2;
            long required = 0;
            foreach (int work in workloads)
                required += (work + (long)rate - 1) / rate;
            if (required <= hours) right = rate;
            else left = rate + 1;
        }
        return left;
    }
}

复杂度： 时间 O(n log M)，额外空间 O(1)，M 为最大工作量。

边界用例： 单个任务；hours 等于任务数；累计小时使用 long。

面试追问：

• 判定函数的单调性具体是什么？

解题思路： 若中点小于右邻居，右侧必有峰值；否则中点或左侧有峰值。

不变量： 当前半开区间中至少存在一个峰值。

public static class AlgCode052Solution
{
    public static int Solve(int[] numbers)
    {
        int left = 0, right = numbers.Length - 1;
        while (left < right)
        {
            int middle = left + (right - left) / 2;
            if (numbers[middle] < numbers[middle + 1])
                left = middle + 1;
            else
                right = middle;
        }
        return left;
    }
}

复杂度： 时间 O(log n)，额外空间 O(1)。

边界用例： 单元素；严格递增；严格递减；多个峰值。

面试追问：

• 如果相邻元素允许相等，当前证明在哪一步失效？