Problem J42: Binary Search / 折半查找

版权信息： · 基础算法题（分治法）

任务总览

题目描述

已知一个长度为 $n$ 的 升序有序表 $R$，请你使用 折半查找（即二分查找） 方法，查找一个给定的关键字 $key$，并输出其在数组中的位置。

输入格式

*第一行包含一个整数 $n$（$1 \leq n \leq 1000$），表示有序表的长度；

• 第二行包含 $n$ 个非负整数（每个数 $\leq 10000$），按照 ​ 升序排列 ​，表示数组 $R[1 \dots n]$；
• 第三行包含一个整数 $key$，表示要查找的关键字。

输出格式

• 如果 $key$ 在数组中存在，输出其 ​ 位置下标（从 1 开始编号） ​；

• 否则输出 -1 表示查找失败。

输入输出样例

输入示例

6
1 3 4 6 8 9
3

输出示例

2

题目分析与解法

✅ 折半查找核心思想：

1. 初始令：low = 1, high = n；
2. 计算中间位置：mid = (low + high) / 2；
3. 比较 $key$ 与 $R[mid]$：

• 若相等：查找成功，返回 mid；

• 若 $key < R[mid]$：说明目标在左半区，更新 high = mid - 1；

  • 若 $key > R[mid]$：说明目标在右半区，更新 low = mid + 1；
  4. 若查找区间为空（low > high），返回 -1。

时间复杂度分析