二分法

1. 区间定义三选一

1
2
3
闭区间 [left, right]     →  left = 0, right = len-1
左闭右开 [left, right)   →  left = 0, right = len
开区间 (left, right)     →  left = -1, right = len

2. 循环条件口诀

1
2
3
闭区间：left <= right    （区间不为空：至少有一个元素）
左闭右开：left < right   （区间不为空：left < right 时还有元素）
开区间：left + 1 < right （区间不为空：中间至少有一个元素）

3. 边界移动口诀

1
2
3
4
5
6
当 nums[mid] < target 时：说明 target 在右边，左边界右移
当 nums[mid] >= target 时：说明 target 在左边（或就是mid），右边界左移

闭区间：left = mid + 1, right = mid - 1
左闭右开：left = mid + 1, right = mid
开区间：left = mid, right = mid

4. 返回值口诀

1
2
找插入位置：返回 left（闭区间、左闭右开）或 right（开区间）
因为循环结束时，left/right 指向第一个 >= target 的位置

📝 记忆表格（最强背诵版）

区间类型 初始化 循环条件 mid < target mid >= target 返回值
闭区间 L=0, R=n-1 L <= R L = mid+1 R = mid-1 L
左闭右开 L=0, R=n L < R L = mid+1 R = mid L
开区间 L=-1, R=n L+1 < R L = mid R = mid R

🎨 形象记忆法

闭区间 [L, R]

想象一根绳子，两端都系着结：

  • 发现 mid 太小 → 把左端绳子往右剪掉一段（L = mid+1）
  • 发现 mid 太大或刚好 → 把右端绳子往左剪掉一段（R = mid-1）
  • 剪到绳子没了（L > R）→ 返回 L（此时 L 就是该插入的位置）

左闭右开 [L, R)

想象左端有结，右端开放：

  • 发现 mid 太小 → 左端移到 mid+1
  • 发现 mid 太大或刚好 → 右端移到 mid（mid 被排除）
  • 最后 L == R → 返回 L

开区间 (L, R)

想象两端都是开放的：

  • L 始终指向 < target 的最右位置
  • R 始终指向 >= target 的最左位置
  • 当 L+1 == R 时停止，返回 R

左闭右开最快但是我觉得闭区间好背诵

只记一种最顺手的！ 我推荐左闭右开，因为它：

  1. 初始化简单（right = len）
  2. 循环条件简单（left < right）
  3. 边界移动规律（right = mid, left = mid+1）
  4. 返回值就是 left
1
2
3
4
5
6
7
8
9
10
11
def searchInsert(self, nums: List[int], target: int) -> int:
    left, right = 0, len(nums)  # [left, right)
    
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1      # 目标在右边
        else:
            right = mid         # 目标在左边或就是mid
    
    return left  # left == right，就是插入位置

针对二维数组如何取

给你一个满足下述两条属性的 m x n 整数矩阵：

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

遍历的时候取index在0到n*m-1之间

1
2

matrix[mid // n][mid % n]