13020 - 二分查找

给定一个长度为 n 的非降序（从小到大）整数序列，请查找某个整数 x 在序列中第一次出现的位置。如果 x 不存在于序列中，则输出 -1。

位置从 1 开始编号。

• 第一行包含一个整数 n （ 1 \le n \le 10^6 ），表示序列的长度。
• 接下来 n 行，每行包含一个整数，表示序列中的元素（已按非降序排列）。
• 最后一行包含一个整数 x ，表示待查找的元素。

输出一个整数，表示 x 第一次出现的位置（从 1 开始），若不存在则输出 -1。

样例说明

序列为 3, 5, 6, 6, 7，查找元素 6，第一次出现的位置是 3（因为第 3 个元素是 6，第 4 个也是 6，但第一次是 3），因此输出 3。

数据范围与约定

• 1 \le n \le 10^6
• 序列元素及 x 均为整数，绝对值不超过 10^9 。
• 序列已按非降序排列。

一本通