二分查找的实现_C++
2021/11/30 17:36:05
本文主要是介绍二分查找的实现_C++,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
二分查找的实现_C++
// 题目描述 1、定义一个顺序存储结构或者数组 2、主函数已经给出,提交代码不需要提交主函数 3、需要完成未给出的二分查找实现 4、中间处理:二分或折半查找,通过二分查找:理解查找成功的ASL和查找失败的ASL。 5、参考程序给出的输出实现二分查找 PS:本题考查二分查找,当然取巧的方式几行代码也能实现,不过不是我们推荐的方式。 int main() { int iArray[MAX_SIZE] = {11,12,13,14,15,26,27,28,29,100}; int iArrayAdd[MAX_SIZE] = {0}; for(int i = 0; i < MAX_SIZE; i++) { iArrayAdd[i]= iArray[i]+1; int isearchRst = binarySearch(iArray, MAX_SIZE, iArrayAdd[i]); if(isearchRst != -1) { cout << iArrayAdd[i] << " is exist, location is " << isearchRst << endl; } else { cout << iArrayAdd[i] << " is not exist!" << endl; } } } 输入 无 ,没有任何输入 输出 查找12第 1 次查找15 查找12第 2 次查找12 12共查找 2次!结果查找:成功! 12 is exist, location is 2 查找13第 1 次查找15 查找13第 2 次查找12 查找13第 3 次查找13 13共查找 3次!结果查找:成功! 13 is exist, location is 3 查找14第 1 次查找15 查找14第 2 次查找12 查找14第 3 次查找13 查找14第 4 次查找14 14共查找 4次!结果查找:成功! 14 is exist, location is 4 查找15第 1 次查找15 15共查找 1次!结果查找:成功! 15 is exist, location is 5 查找16第 1 次查找15 查找16第 2 次查找28 查找16第 3 次查找26 16共查找 3次!结果查找:失败! 16 is not exist! 查找27第 1 次查找15 查找27第 2 次查找28 查找27第 3 次查找26 查找27第 4 次查找27 27共查找 4次!结果查找:成功! 27 is exist, location is 7 查找28第 1 次查找15 查找28第 2 次查找28 28共查找 2次!结果查找:成功! 28 is exist, location is 8 查找29第 1 次查找15 查找29第 2 次查找28 查找29第 3 次查找29 29共查找 3次!结果查找:成功! 29 is exist, location is 9 查找30第 1 次查找15 查找30第 2 次查找28 查找30第 3 次查找29 查找30第 4 次查找100 30共查找 4次!结果查找:失败! 30 is not exist! 查找101第 1 次查找15 查找101第 2 次查找28 查找101第 3 次查找29 查找101第 4 次查找100 101共查找 4次!结果查找:失败! 101 is not exist! 样例输入 Copy 样例输出 Copy 查找12第 1 次查找15 查找12第 2 次查找12 12共查找 2次!结果查找:成功! 12 is exist, location is 2 查找13第 1 次查找15 查找13第 2 次查找12 查找13第 3 次查找13 13共查找 3次!结果查找:成功! 13 is exist, location is 3 查找14第 1 次查找15 查找14第 2 次查找12 查找14第 3 次查找13 查找14第 4 次查找14 14共查找 4次!结果查找:成功! 14 is exist, location is 4 查找15第 1 次查找15 15共查找 1次!结果查找:成功! 15 is exist, location is 5 查找16第 1 次查找15 查找16第 2 次查找28 查找16第 3 次查找26 16共查找 3次!结果查找:失败! 16 is not exist! 查找27第 1 次查找15 查找27第 2 次查找28 查找27第 3 次查找26 查找27第 4 次查找27 27共查找 4次!结果查找:成功! 27 is exist, location is 7 查找28第 1 次查找15 查找28第 2 次查找28 28共查找 2次!结果查找:成功! 28 is exist, location is 8 查找29第 1 次查找15 查找29第 2 次查找28 查找29第 3 次查找29 29共查找 3次!结果查找:成功! 29 is exist, location is 9 查找30第 1 次查找15 查找30第 2 次查找28 查找30第 3 次查找29 查找30第 4 次查找100 30共查找 4次!结果查找:失败! 30 is not exist! 查找101第 1 次查找15 查找101第 2 次查找28 查找101第 3 次查找29 查找101第 4 次查找100 101共查找 4次!结果查找:失败! 101 is not exist!
// #include<iostream> using namespace std; #define MAX_SIZE 10 //最大长度 typedef int KeyType; //定义关键字类型为int int binarySearch(int* pArray, int n, KeyType k) //折半查找算法 { int low = 0, high = n - 1, mid, chaci = 0; while (low <= high) //当前区间存在元素时循环 { chaci = chaci + 1; mid = (low + high) / 2; if (k == pArray[mid]) { //查找成功返回其逻辑序号mid+1 cout << "查找" << k << "第 " << chaci << " 次查找" << pArray[mid] << endl; cout << k << "共查找 " << chaci << "次!结果查找:成功!" << endl; return mid + 1; } else if (k < pArray[mid]) { //继续在R[low..mid-1]中查找 high = mid - 1; cout << "查找" << k << "第 " << chaci << " 次查找" << pArray[mid] << endl; } else { //k>R[mid].key low = mid + 1; cout << "查找" << k << "第 " << chaci << " 次查找" << pArray[mid] << endl; } //继续在R[mid+1..high]中查找 } cout << k << "共查找 " << chaci << "次!结果查找:失败!" << endl; return -1; //未找到时返回0(查找失败) }
这篇关于二分查找的实现_C++的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-29document对象教程:新手入门指南
- 2024-09-29端到端的 AWS DevOps 项目:使用 ECR 和 RDS 的 ECS Fargate 的 CI/CD 管道
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享