二分

0 Binary Search Basic 什么是二分查找？ 二分查找（Binary Search）是在有序数据中通过每次排除一半来快速定位目标的算法。时间复杂度 O(log n) 适用条件： 数据有序（或具有某种单调性/二段性） 能通过中间元素判断答案在哪一半 模板一： 1l, r = 0, n - 1 # 闭区间 [l, r]；值域二分时换成 值域下界, 值域上界 2while l < r: 3 mid = (l + r) // 2 4 if check(mid): 5 r = mid # mid 可能是答案，保留 6 else: 7 l = mid + 1 # mid 一定不是答案，排除 8return l # 退出时 l == r 模板二： 1l, r = 0, n - 1 2while l < r: 3 mid = (l + r + 1) // 2 4 if check(mid): 5 l = mid 6 else: 7 r = mid - 1 8return l 二分一定有解，但是不一定是题目的解 二分的解一定属于[0, n - 1]，但是答案可能是- 1 or n，在循环外考虑 二分答案的三步套路 确认答案可分 ： 大了行小了不行(或反过来) 写 check(x) ：通常是 O(n) 的模拟或贪心 定 l, r 的值域：下界取最小合法值,上界取一个保证可行的值 1 二分模板 1.1 搜索插入位置 | Easy 题目：排序数组 + target,存在返回下标,不存在返回按序插入的位置。要求 O(log n) ...