#12029. Binary Search / 折半查找

Binary Search / 折半查找

Problem J42: Binary Search / 折半查找

版权信息: · 基础算法题(分治法)


任务总览

任务名称 时间限制 内存限制 分数
折半查找 1 sec 1024 MB 10 points

题目描述

已知一个长度为 nn 的 升序有序表 RR,请你使用 折半查找(即二分查找) 方法,查找一个给定的关键字 keykey,并输出其在数组中的位置。


输入格式

*第一行包含一个整数 nn1n10001 \leq n \leq 1000),表示有序表的长度;

  • 第二行包含 nn 个非负整数(每个数 10000\leq 10000),按照 ​ 升序排列 ​,表示数组 R[1n]R[1 \dots n]
  • 第三行包含一个整数 keykey,表示要查找的关键字。

输出格式

  • 如果 keykey 在数组中存在,输出其 ​ 位置下标(从 1 开始编号) ​;

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


输入输出样例

输入示例

6
1 3 4 6 8 9
3

输出示例

2

题目分析与解法

✅ 折半查找核心思想:

  1. 初始令:low = 1, high = n
  2. 计算中间位置:mid = (low + high) / 2
  3. 比较 keykeyR[mid]R[mid]
  • 若相等:查找成功,返回 mid

  • key<R[mid]key < R[mid]:说明目标在左半区,更新 high = mid - 1

    • key>R[mid]key > R[mid]:说明目标在右半区,更新 low = mid + 1
    1. 若查找区间为空(low > high),返回 -1

时间复杂度分析

操作 复杂度
查找一次 O(logn)O(\log n)
多次查找 O(mlogn)O(m \log n)mm 次查询)