有一个升序数组 nums，长度 n = 10^6，允许有重复元素（例如 [1,2,2,2,3,5]）。写一个函数返回 target 第一次出现的下标，不存在返回 -1。请说明你的循环不变量是什么、while 条件写 lo < hi 还是 lo <= hi、为什么 hi 的更新是 hi = mid 而不是 hi = mid - 1，以及 mid 怎么算。

面试官在考什么

判断候选人是否真理解二分的边界不变量，还是只会在没有重复元素时写"找到就返回"的模板。

二分查找

回答框架 · 前两步

1. 循环不变量：答案（第一个等于 target 的下标，或者说 lower_bound 的位置）始终落在搜索区间内；建议用左闭右开 [lo, hi)，初始 lo=0、hi=n。
2. 用 while (lo < hi)、mid = lo + (hi-lo)/2（下取整）、hi = mid：这样收敛到左边界且不会死循环；若写 hi = mid - 1 会把可能的答案跳过去。

延伸阅读

• 避坑与冲刺：简历自洽、六种扣分话术、D-7 准备表

想看这个方向的整体准备路线？ 进入「数据结构与算法」方向页

同一能力域的其他题

• 一个 N×N 的 0/1 网格，N=2000（共 400 万格），0 表示可通行，1 表示障碍，允许上下左右四方向移动，每走一格算 1 步。要求从 (0,0) 走到 (N-1,N-1)，给出最短步数，不可达返回 -1。内存上限 256MB。请说明你选 BFS 还是 DFS、队列和 visited 怎么设计、以及 visited 具体在什么时刻打标记。
• 社交关系图共 10^9 个用户，平均出度 200，边存放在分布式 KV 上（一次邻居查询约 5ms），单机可用内存 64GB。现在要找出指定用户 A 的 3 度以内（含 3 度）的全部用户 ID。你选 BFS 还是 DFS？写出你的遍历控制逻辑，估算 frontier（当前层待扩展集合）的最大规模，并说明用什么结构做去重。
• 你接手一个权限可达性服务：授权图约 500 万节点、2000 万条有向边（用户→角色→权限组→资源），业务上允许成环。线上要回答『用户 u 能否到达资源 r』，峰值 10 万 QPS、P99 要求 20ms。上一版实现是每次请求从 u 出发做一次 DFS，线上大面积超时并偶发栈溢出。请给出你的方案、演进路径和取舍。
• 给你一个 1000×1000 的 0/1 网格（1 是陆地，0 是水），上下左右相邻的陆地属于同一个岛，要求返回岛屿数量。A 同学用递归 DFS 做 flood fill，样例全过，但把规模放大到接近满屏陆地时程序崩溃。请说明崩溃的原因，写出你会怎么改；并说明同一份数据用 BFS 写时，队列规模的最坏情况是什么量级。
• 有向图有 4 个节点 s、a、b、t，边和权值是：s→a = 1，s→b = 2，b→a = -2，a→t = 3，b→t = 10。用朴素 Dijkstra（每次从未确定的节点里取 dist 最小的那个标记为已确定，之后不再更新它的 dist）从 s 求到 t 的最短路。请说出它算出的 dist[t] 是多少、正确答案是多少、差在哪一步上，然后说明什么样的图 Dijkstra 才是安全的。
• 一个城市路网约 10^8 个节点、2.5×10^8 条边，边权是通行时间（非负，但按早晚高峰每 5 分钟整体更新一次）。要支持单点到单点最短路查询、峰值 10^4 QPS、P99 延迟 < 50ms。朴素 Dijkstra 单次查询要扫描大量节点。你怎么选算法与架构？说清预处理成本、查询延迟、以及权重频繁变化带来的矛盾怎么权衡。