CJBS01｜编号首次出现 题解

核心算法

在有序数组中二分查找第一个满足 $a_i\ge x$ 的位置。

思路推导

对固定的 $x$，条件 $a_i\ge x$ 随下标呈现“前面不满足、后面满足”的单调性。找到第一个满足位置 pos 后，再检查 a[pos] == x。相等则它就是第一次出现的位置，否则数组中没有 $x$。

正确性说明

二分始终保留第一个可能满足 $a_i\ge x$ 的位置。循环结束时，left 左侧全部小于 $x$，left 自身是首个不小于 $x$ 的位置。因此若 a[left]==x，它必为第一次出现；若不相等，则不存在 $x$。

复杂度

• 每次查询时间复杂度：$O(\log n)$；
• 总时间复杂度：$O(q\log n)$；
• 额外空间复杂度：$O(1)$。

易错点

• 题目要第一次出现的位置，不是任意一个位置；
• 输出位置从 $1$ 开始；
• 二分结束后必须检查是否真的等于 $x$；
• 要覆盖 $x$ 小于最小值、大于最大值和全数组相等的情况。