【数据结构——查找】二分查找(头歌实践教学平台习题)【合集】

server/2024/12/18 1:44:28/

目录😋

任务描述

相关知识

测试说明

我的通关代码:

测试结果:


任务描述

本关任务:实现二分查找算法

相关知识

为了完成本关任务,你需要掌握:1.根据键盘输入的一组有序数据建立顺序表,2.顺序表的输出,3.二分查找算法

提示:二分查找算法中要依次输出每次查找的区间,及与k所比较的关键字,用空格分隔开。假设顺序表的关键字序列: 2 3 10 15 20 25 28 29 30 35 40,

如果要查找的关键字k=20,则函数输出如下,并返回值5.
第1次比较: 查找范围R[0...10],比较元素R[5]:25
第2次比较: 查找范围R[0...4],比较元素R[2]:10
第3次比较: 查找范围R[3...4],比较元素R[3]:15
第4次比较: 查找范围R[4...4],比较元素R[4]:20

如果要查找的关键字k=26,则函数要输出如下,并返回值0.
第1次比较: 查找范围R[0...10],比较元素R[5]:25
第2次比较: 查找范围R[6...10],比较元素R[8]:30
第3次比较: 查找范围R[6...7],比较元素R[6]:28

测试说明

平台会对你编写的代码进行测试:

测试输入示例:
1 2 3 4 5 6 7 8 9 10 
9
(说明:第一行是输入的一组原始关键字数据,第二行是要查找的关键字)

预期输出:

请输入一组数据 : 关键字序列:1 2 3 4 5 6 7 8 9 10
请输入要查找的关键字 :9
查找9的比较过程如下:
第1次比较:在[0,9]中比较元素R[4]:5
 第2次比较:在[5,9]中比较元素R[7]:8
 第3次比较:在[8,9]中比较元素R[8]:9
元素9的位置是9

开始你的任务吧,祝你成功!


我的通关代码:

#include <iostream>
#include <vector>
using namespace std;
// 定义查找元素的结构体类型,包含关键字和其他数据(这里暂未详细使用其他数据部分)
struct RecType {int key;// 可以按需添加其他数据成员及对应操作,此处简化只关注关键字key
};// 创建顺序表,将输入的关键字数据存入顺序表中
void CreateList(vector<RecType> &R, const vector<int> &keys) {for (size_t i = 0; i < keys.size(); ++i) {RecType temp;temp.key = keys[i];R.push_back(temp);}
}// 输出顺序表的函数,遍历顺序表并输出每个元素的关键字
void DispList(const vector<RecType> &R) {for (size_t i = 0; i < R.size(); ++i) {cout << R[i].key << " ";}cout << endl;
}// 二分查找算法实现,按照要求输出每次查找的区间及比较的关键字
int BinSearch(const vector<RecType> &R, int k) {int low = 0;int high = R.size() - 1;int count = 1;while (low <= high) {int mid = low + (high - low) / 2;cout << "  第" << count << "次比较:在[" << low << "," << high<< "]中比较元素R[" << mid << "]:" << R[mid].key << endl;if (R[mid].key == k) {return mid + 1; // 返回位置,这里的位置是从1开始计数,所以下标加1} else if (R[mid].key > k) {high = mid - 1;} else {low = mid + 1;}count++;}return 0; // 如果没找到,返回0表示元素不在表中
}int main() {vector<RecType> R;vector<int> keys;int n =10; // 根据测试示例,这里默认输入数据个数为10,也可以改成让用户输入个数cout << "请输入一组数据 :" << endl;for (int i = 0; i < n; ++i) {int num;cin >> num;keys.push_back(num);}CreateList(R, keys);cout << "关键字序列:";DispList(R);int k;cin >> k;cout << "请输入要查找的关键字 :" << k << endl;cout << "查找" << k << "的比较过程如下:" << endl;int result = BinSearch(R, k);if (result != 0) {cout << "元素" << k << "的位置是" << result << endl;} else {cout << "元素" << k << "不在表中" << endl;}return 0;
}

测试结果:

在这里插入图片描述


http://www.ppmy.cn/server/151047.html

相关文章

海康威视监控web实时预览解决方案

海康威视摄像头都试rtsp流&#xff0c;web页面无法加载播放&#xff0c;所以就得转换成web页面可以播放的hls、rtmp等数据流来播放。 一&#xff1a;萤石云 使用萤石云平台&#xff0c;把rtsp转化成ezopen协议&#xff0c;然后使用组件UIKit 最佳实践 萤石开放平台API文档 …

自动驾驶系统研发系列—智能驾驶新高度:解析ESS驾驶员转向辅助系统

🌟🌟 欢迎来到我的技术小筑,一个专为技术探索者打造的交流空间。在这里,我们不仅分享代码的智慧,还探讨技术的深度与广度。无论您是资深开发者还是技术新手,这里都有一片属于您的天空。让我们在知识的海洋中一起航行,共同成长,探索技术的无限可能。 🚀 探索专栏:学…

【AI知识】有监督学习分类任务之支持向量机

1.支持向量机概念 支持向量机&#xff08;Support Vector Machine, SVM&#xff09; 是一种有监督学习算法&#xff0c;主要用于分类任务&#xff08;也可用于回归任务&#xff0c;即支持向量回归&#xff0c;SVR&#xff09;。SVM的核心思想是找到一个最优的超平面&#xff0…

Redis Cluster 分片机制

Redis 集群是 Redis 提供的一种分布式实现&#xff0c;用于水平扩展数据存储能力。通过 Redis 集群&#xff0c;可以将数据分片存储在多个 Redis 节点上&#xff0c;同时提供高可用性和故障转移功能。 分片&#xff08;Sharding&#xff09;&#xff1a; Redis 集群将数据划分…

leetcode---mysql

619. 只出现一次的最大数字 - 力扣&#xff08;LeetCode&#xff09; MyNumbers 表&#xff1a; ------------------- | Column Name | Type | ------------------- | num | int | ------------------- 该表可能包含重复项&#xff08;换句话说&#xff0c;在SQL中&…

外卖开发(八)—— SpringTask(定时任务) 和 WebSocket网络协议

外卖开发&#xff08;八&#xff09;—— SpringTask 和 WebSocket 一、利用SpringTask完成定时任务1、cron表达式2、springtask实现 二、使用webSocket实现接单、催单提醒1、代码分析2、催单提醒 一、利用SpringTask完成定时任务 Spring Task是Spring框架提供的任务调度工具&…

Scala——泛型

背景&#xff1a;你是一个程序员&#xff0c;老板让你写一个函数&#xff0c;用来获取列表中的中间元素 定义函数的格式&#xff1a; def 函数名字&#xff08;参数1&#xff1a;类型1&#xff09;&#xff1a;返回值的类型{} package test40 //泛型 //List&#xff08;1,2,3…

ADB在浏览器中:ya-webadb项目安装与配置完全指南

ADB在浏览器中&#xff1a;ya-webadb项目安装与配置完全指南 ya-webadb ADB in your browser [这里是图片001] 项目地址: https://gitcode.com/gh_mirrors/ya/ya-webadb 项目基础介绍与编程语言 ya-webadb 是一个由 Yume-chan 开发的开源项目&#xff0c;它实现了ADB&#x…