LeetCode 0 · 二分查找认知实验室

题目描述：给定一个升序整型数组 arr 和目标值 target，实现递归二分查找，返回目标下标，若不存在返回 -1。分析其时间复杂度。

int search(int start, int end, int target, int *arr) {
    if (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == target) return mid;
        else if (target > arr[mid])
            return search(mid + 1, end, target, arr);
        else if (target < arr[mid])
            return search(start, mid - 1, target, arr);
    }
    return -1;
}

输入：升序数组，目标值 输出：下标或 -1

约束：数组长度 n ≥ 1，元素为整数。

要求：时间复杂度 O(log n)，空间复杂度 O(log n)（递归栈）。

🔍 阶段1-3：理解 · 暴力 · 瓶颈

二分查找

认知任务： 观察递归二分过程，理解每次搜索区间减半，从而推导复杂度。

点击“下一步”开始追踪

🧠 瓶颈思考

每次递归将搜索范围缩小一半，因此比较次数为 log₂(n) 级别。

📐 核心表示 & 不变量

不变量： 在每一轮递归中，arr[start..end] 保持有序，且 target 只可能存在于该区间内。

关键变量： low, high, mid，每次排除一半。

mid = low + (high - low) / 2

⌨️ 代码补全 (Python)

def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

🧪 迁移练习 · LeetCode 713 乘积小于 K 的子数组

题意：给定正整数数组 nums 和整数 k，返回子数组乘积小于 k 的连续子数组个数。

示例： nums = [10,5,2,6], k = 100 → 8

约束： 0 < nums[i] ≤ 1000, 0 < k ≤ 10⁶

📋 读题检查

1. 子数组必须连续吗？

2. 乘积小于 k 是否包含等于？

🔁 原题 vs 迁移题

保留点

滑动窗口/双指针
窗口内维护某个性质
O(n) 时间复杂度

变化点

从求和变为求乘积
计数方式：right-left+1
需要维护 product

请点击确认：

🧩 算法拼装 (滑动窗口)

槽位1： 初始化 left=0, product=1, ans=0 参考答案: left=0, product=1, ans=0

槽位2： 遍历 right 从 0 到 n-1 参考答案: for right in range(len(nums))

槽位3： product *= nums[right] 参考答案: product *= nums[right]

槽位4： 当 product >= k 时移动 left 参考答案: while product >= k and left <= right: product //= nums[left]; left += 1

槽位5： ans += right - left + 1 参考答案: ans += right - left + 1

🎬 迁移样例逐帧动画

迁移动画

📌 迁移总结

原题 Skill： 二分查找通过区间减半达到 O(log n)。

迁移到 713： 滑动窗口通过维护乘积 product，固定 right 时，满足条件的 left 到 right 区间内所有子数组都合法，计数为 right-left+1。

新证明义务： 证明当 product < k 时，所有以 right 结尾的子数组均满足条件，且窗口内不遗漏。

🎯 最终 Skill 卡

题号：0 (二分查找) → 迁移 713

触发信号：有序数组查找 → 子数组乘积计数

核心表示：二分区间 [left,right] / 滑动窗口 [left,right] 与 product

关键不变量：二分：target 在区间内；滑动窗口：product < k 时窗口内所有子数组合法

复杂度：二分 O(log n)；滑动窗口 O(n)

常见错误：忘记更新 product 或 left 移动时未除 nums[left]

可迁移题型：子数组和、最小覆盖子串

LeetCode #0 · 二分查找 · 时间复杂度分析