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

中等数组二分查找递归

英文: Binary Search (Time Complexity)

题目描述：给定一个升序整型数组 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;
}

函数签名： int search(int start, int end, int target, int *arr)

约束： 数组长度 n ≥ 1，元素升序。

要求： 分析时间复杂度，并理解二分查找的递归不变量。

🧪 阶段1 · 理解题目 & 暴力体验

认知目标： 手动执行一次二分查找，感受每次比较缩小一半搜索范围。

🔍 模拟二分查找

low=0 mid=2 high=5 比较次数=0

目标值: 7 (数组 [1,3,5,7,9,11])

❓ 问题

第一次比较后，搜索区间变为？

⚡ 阶段2 · 发现瓶颈

为什么暴力线性扫描不够好？ 对于 n=1e6，线性查找最坏比较1e6次，而二分查找只需约 log₂(1e6) ≈ 20 次。

💡 核心不变量： 每次循环/递归调用前，如果 target 存在，则一定在区间 [low, high] 内。

问题： 二分查找每次比较后，区间大小变为原来的多少？

🧠 阶段3 · 优化表示 & 代码

表示： 使用 low, high, mid 维护搜索区间。

def search(start, end, target, arr):
    if start > end:
        return -1
    mid = (start + end) // 2
    if arr[mid] == target:
        return mid
    elif target > arr[mid]:
        return search(mid+1, end, target, arr)
    else:
        return search(start, mid-1, target, arr)

不变量： 进入递归时，target 若存在必在 [start, end] 中。

# 时间复杂度 O(log n)，空间复杂度 O(log n) 递归栈
def binary_search(arr, target):
    def helper(l, r):
        if l > r: return -1
        m = (l + r) // 2
        if arr[m] == target: return m
        if arr[m] < target: return helper(m+1, r)
        return helper(l, m-1)
    return helper(0, len(arr)-1)

🚀 阶段4 · 迁移练习：LeetCode 713 乘积小于 K 的子数组

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

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

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

变化点： 从“和”变为“乘积”，计数方式为 right-left+1。

🔧 算法拼装

① 初始化： left=0, product=1, ans=0 left=0, product=0, ans=0 left=0, product=1, ans=1

② 循环条件： for right in range(len(nums)) while left < len(nums) for right in range(1, len(nums))

③ 更新乘积： product *= nums[right] product += nums[right] product = nums[right]

④ 收缩条件： while product >= k and left <= right: while product > k: if product >= k:

def numSubarrayProductLessThanK(nums, k):
    if k <= 1: return 0
    left = 0; product = 1; ans = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k:
            product //= nums[left]
            left += 1
        ans += right - left + 1
    return ans

🎬 迁移样例逐帧动画

🏆 Skill 总结

核心不变量： 滑动窗口内所有元素的乘积 < k。

触发信号： 连续子数组、乘积/和小于某值。

核心操作： 右指针扩展，左指针收缩，计数 += right-left+1。

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

迁移方向： 和小于K的子数组、最大连续乘积等。