Problem: 有序数组中的二分查找

任务总览

题目描述

请在一个有序递增的数组中（数组中​不存在相同元素​​），采用​二分查找​，找出值 x 所在的位置。如果 x 在数组中不存在，请输出 -1。

注意：位置从 1 开始计数。

输入格式

• 第一行：一个整数 n $(1 ≤ n ≤ 10^6)$，表示数组的长度。
• 第二行：n 个递增的整数，表示数组的元素（$1 ≤ a\_i ≤ 10^8$，元素互不相同）。
• 第三行：一个整数 x $(0 ≤ x ≤ 10^8)$，表示要查找的目标值。

输出格式

• 输出一个整数，表示 x 在数组中的位置（从 1 开始编号），若不存在 x，输出 -1。

输入输出示例

输入示例 1

10
1 3 5 7 9 11 13 15 17 19
3

输出示例 1

2

题目解析

• 由于数组已排序且无重复值，适合使用​二分查找算法​，时间复杂度为 $O(\log n)$。
• 可采用递归或非递归方式实现，分别在左半区或右半区继续查找，直到找到目标值或确定不存在。

数据范围

• 数组长度 $n \leq 10^6$
• 每个数组元素为不超过 $10^8$ 的正整数
• 查找目标 x 的取值范围为 $0 ≤ x ≤ 10^8$