c++折半查找算法(实验类型:验证型) 1)问题描述:从键盘读入一串整数和一个待查关键
时间: 2024-01-03 22:02:03 浏览: 97
C++实现折半查找
5星 · 资源好评率100%
折半查找算法,也称为二分查找算法,是一种高效的查找方法。该算法适用于已排好序的列表,通过将待查关键字与列表中间的关键字比较,确定待查关键字在列表中的位置,从而缩小了查找范围。
算法步骤如下:
1. 从键盘读入一串整数,将其存储在一个有序列表中。
2. 读入待查关键字。
3. 定义列表的起始索引start为0,结束索引end为列表长度减1。
4. 当start小于等于end时,执行以下步骤。
- 将中间索引mid定义为(start + end)除以2。
- 如果列表中间关键字等于待查关键字,那么返回中间索引。
- 如果列表中间关键字大于待查关键字,那么将end更新为mid-1。
- 如果列表中间关键字小于待查关键字,那么将start更新为mid+1。
5. 若循环结束仍未找到待查关键字,则返回-1表示未找到。
通过实验验证折半查找算法:
假设输入的一串整数为:[2, 4, 6, 8, 10, 12, 14, 16, 18, 20],待查关键字为12。
1. 按照算法步骤,设置start=0, end=9。
2. 中间索引为4,对应的关键字为10,小于12,将start更新为mid+1,即5。
3. 中间索引为7,对应的关键字为16,大于12,将end更新为mid-1,即6。
4. 中间索引为5,对应的关键字为12,等于12,返回中间索引5,表示找到关键字。
5. 实验验证成功。
折半查找算法的时间复杂度为O(logN),N表示列表的长度,相对于线性查找算法,折半查找算法的效率更高。
阅读全文