二分查找

维护区间 [l, r],每次取中点 mid 和 target 比:nums[mid] 小了说明答案只在右边,l = mid + 1;大了只在左边,r = mid - 1;相等就命中。7 个数最多比 3 次。前提是数组必须有序——无序数组上二分结果完全错误而且不报错,是最隐蔽的 WA。

有重复元素时,机试常要的不是「随便命中一个」,而是边界位置。stdlib.h 的 bsearch 命中的是任意一个相等元素,不保证最左,拿它求边界会时对时错——所以求边界只能手写。lowerBound 返回第一个 >= x 的位置:定位等于 x 的左边界;x 不存在时给出该插到哪,永远不会失败,比「命中/未命中」二元结果好用得多。

数组 {1, 3, 5, 7, 7, 9, 11} 里:lowerBound(7) = 3 是第一个 7;lowerBound(8) = 5 是第一个严格大于 7 的位置(整数场景下即第一个 >= 8);两者相减 5 - 3 = 2 正好是 7 的出现次数。写法要点:r 初始为 n、循环条件 l < r,a[mid] >= x 时 r = mid(mid 自己可能是答案,不能扔),否则 l = mid + 1,最后返回 l。