题目重点：用半开搜索区间证明二分终止与插入位置，覆盖重复值和目标在两端外。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练数组升序允许重复，返回第一个≥target的位置；不存在则返回n。
- 不实际插入，不自动排序；空数组返回0。
- “最小位置”按lower_bound解释，同值要插在第一份重复之前。
解题路线
- 答案p是小于target的元素数量，满足[0,p)全部<target、[p,n)全部≥target。它允许为n，所以不能只在存在的元素下标中搜索。
- 维护[left,right)未决区间，初始0,n；不变量是left之前全<target，right及其后全≥target。mid=(left+right)//2，比较一次即可排除一半。
- 若values[mid]<target，mid也不能是答案，left=mid+1；否则mid可能是第一个合格，right=mid而不是mid−1。右侧边界不变量保留当前合格候选。
- 每次left<right时mid处于合法数组下标，且区间长度严格缩小；终止left=right，未决区间为空，两侧不变量使此位置唯一满足分界。
- 目标等于重复值时持续向左压right，因此找到首份。同一函数用于严格LIS替换；upper_bound只需把比较改为≤target，但它回答的是另一个分界。
- 二分要求随机访问及已排序比较关系；链表每次找mid可能线性，不再保证O(log n)总时间。实际往Python list插入则还要移动后续元素，不能把找位置的复杂度当整个插入复杂度。
手动走一遍
[1,2,2,4]查2返回1，查3返回3，查5返回4，查0返回0；空数组查任意值0。循环不读取values[n]，n只作为合法返回位置。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def lower_bound(values, target):
left, right = 0, len(values)
while left < right:
mid = (left + right) // 2
if values[mid] < target:
left = mid + 1
else:
right = mid
return left
def lis_length(values):
tails = []
for value in values:
position = lower_bound(tails, value)
if position == len(tails):
tails.append(value)
else:
tails[position] = value
return len(tails)
复杂度
O(log(n+1))比较时间，O(1)工作空间；数组排序不在此操作内。真实动态数组插入另需O(n)移动。
易错点与追问
容易失分的边界
- 等值时向右走变upper_bound。
- 半开区间却right=mid−1漏候选。
- 空数组或答案n时访问越界。
- 把二分位置计算当作常量移动插入。
继续深挖
- upper_bound怎样变更？
- 如何用两个边界求某值出现次数？
- 比较器不是全序时需要什么保证？
- 链表或远程分页数据如何适配？
