怎么学习企业网站维护,网站建设的空间选择,成都微信微网站建设,网站开发的安全性主要考虑哪些目录#x1f60b;
任务描述
相关知识
测试说明
我的通关代码:
测试结果#xff1a; 任务描述 本关任务#xff1a;实现二分查找的算法。 相关知识 为了完成本关任务#xff0c;你需要掌握#xff1a;1.根据键盘输入的一组有序数据建立顺序表#xff0c;2.顺序表的输…目录
任务描述
相关知识
测试说明
我的通关代码:
测试结果 任务描述 本关任务实现二分查找的算法。 相关知识 为了完成本关任务你需要掌握1.根据键盘输入的一组有序数据建立顺序表2.顺序表的输出3.二分查找算法。 提示二分查找算法中要依次输出每次查找的区间及与k所比较的关键字用空格分隔开。假设顺序表的关键字序列: 2 3 10 15 20 25 28 29 30 35 40 如果要查找的关键字k20则函数输出如下并返回值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 如果要查找的关键字k26则函数要输出如下并返回值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(vectorRecType R, const vectorint keys) {for (size_t i 0; i keys.size(); i) {RecType temp;temp.key keys[i];R.push_back(temp);}
}// 输出顺序表的函数遍历顺序表并输出每个元素的关键字
void DispList(const vectorRecType R) {for (size_t i 0; i R.size(); i) {cout R[i].key ;}cout endl;
}// 二分查找算法实现按照要求输出每次查找的区间及比较的关键字
int BinSearch(const vectorRecType 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() {vectorRecType R;vectorint 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;
}测试结果
