#12029. Binary Search / 折半查找
Binary Search / 折半查找
Problem J42: Binary Search / 折半查找
版权信息: · 基础算法题(分治法)
任务总览
任务名称 | 时间限制 | 内存限制 | 分数 |
---|---|---|---|
折半查找 | 1 sec | 1024 MB | 10 points |
题目描述
已知一个长度为 的 升序有序表 ,请你使用 折半查找(即二分查找) 方法,查找一个给定的关键字 ,并输出其在数组中的位置。
输入格式
*第一行包含一个整数 (),表示有序表的长度;
- 第二行包含 个非负整数(每个数 ),按照 升序排列 ,表示数组 ;
- 第三行包含一个整数 ,表示要查找的关键字。
输出格式
-
如果 在数组中存在,输出其 位置下标(从 1 开始编号) ;
-
否则输出
-1
表示查找失败。
输入输出样例
输入示例
6
1 3 4 6 8 9
3
输出示例
2
题目分析与解法
✅ 折半查找核心思想:
- 初始令:
low = 1
,high = n
; - 计算中间位置:
mid = (low + high) / 2
; - 比较 与 :
-
若相等:查找成功,返回
mid
; -
若 :说明目标在左半区,更新
high = mid - 1
;- 若 :说明目标在右半区,更新
low = mid + 1
;
- 若查找区间为空(
low > high
),返回-1
。
- 若 :说明目标在右半区,更新
时间复杂度分析
操作 | 复杂度 |
---|---|
查找一次 | |
多次查找 | ( 次查询) |