二分查找时间复杂度分析

📌 本题训练的核心认知：通过递归树观察二分查找每次将搜索区间减半，从而推导出 O(log n) 的时间复杂度。你将亲手操作递归过程，并迁移到“乘积小于K的子数组”滑动窗口计数。

🔍 递归搜索可视化

low: 0

high: 7

mid: 3

target: 7

比较次数: 0

当前状态: 准备

递归深度：0 / 最大深度 log₂(n)+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;

🧠 认知任务

🚀 迁移练习：乘积小于 K 的子数组 (LeetCode 713)

📋 原题 vs 迁移题

保留点：滑动窗口、右指针扩展、左指针收缩

变化点：求和→求积；计数方式；窗口内元素乘积

我确认理解保留点
我确认理解变化点

🔧 算法拼装 (选择正确表达式)

窗口乘积 product 更新：

收缩条件：

计数方式：

🎬 迁移逐帧动画

📌 迁移总结

原题二分查找通过区间减半达到 O(log n)。迁移题滑动窗口通过右指针固定，左指针收缩，利用乘积单调性，每次右移右指针时，新增子数组数量为 right-left+1。

新证明义务：证明窗口内所有以 right 结尾的子数组乘积都小于 k。

📇 Skill 卡

题型：二分查找 / 递归复杂度分析
触发信号：有序数组、查找目标、递归分治
核心表示：递归树、区间 [low, high]
关键不变量：每次递归区间长度减半，比较次数 = 递归深度
核心操作：mid = low + (high-low)/2
复杂度：时间 O(log n)，空间 O(log n) 递归栈
常见错误：忘记更新边界导致死循环；误认为 O(n)
迁移方向：滑动窗口计数、二分答案
推荐下一题：LeetCode 209, 713

⚡ 二分查找时间复杂度分析

🔍 递归搜索可视化

🧠 认知任务

🚀 迁移练习：乘积小于 K 的子数组 (LeetCode 713)

📇 Skill 卡