Binary Search--二分查找
-- 查找 二分 search Binary
2023-09-11 14:15:22 时间
Binary Search--二分查找
采用二分法查找时,数据需是排好序的。 基本思想:假设数据是按升序排序的,对于给定值x,从序列的中间位置开始比较,如果当前位置值等于x,则查找成功;若x小于当前位置值,则在数列的前半段 中查找;若x大于当前位置值则在数列的后半段中继续查找,直到找到为止。
二分法查找在针对大量有序排列的情况下发挥出很优越的效率,其时间复杂度O(lgN)。
代码:
1 /* 2 Author:Mengmeng 3 Time:2016-6-27 23:33:49 4 Description: 5 采用二分法查找时,数据需是排好序的。 6 基本思想:假设数据是按升序排序的,对于给定值x,从序列的中间位置开始比较, 7 如果当前位置值等于x,则查找成功;若x小于当前位置值,则在数列的前半段 中查找; 8 若x大于当前位置值则在数列的后半段中继续查找,直到找到为止。 9 */ 10 #include <iostream> 11 using namespace std; 12 13 14 int BinarySearch(int data[],int min,int max,int dest,bool UpOrDown) 15 { 16 int mid = 0; 17 if (min > max)//递归结束条件 18 { 19 cout << "找不到" << dest << "!"<<endl; 20 return -1; 21 } 22 mid = (max + min) / 2; 23 if (dest == data[mid])//递归结束条件 24 return mid; 25 if (UpOrDown == true)//升序排列 26 { 27 if (dest < data[mid])//递归条件 28 return BinarySearch(data, min, mid - 1, dest, true); 29 else 30 return BinarySearch(data, mid + 1, max, dest, true); 31 } 32 else//降序排列 33 { 34 if (dest < data[mid]) 35 return BinarySearch(data, mid + 1, max, dest, false); 36 else 37 return BinarySearch(data, min, mid - 1, dest, false); 38 } 39 40 41 42 } 43 int main(void) 44 { 45 int data1[] = { 0, 11, 22,33,44,55,66,77,88,99 }; 46 int data2[] = { 99, 88, 77, 66, 55, 44, 33, 22, 11, 0 }; 47 #if 0 48 cout << "请参照下列数字:" << endl; 49 cout<< "{"; 50 int len = sizeof(data1) / sizeof(int); 51 for (int i = 0; i < len; i++) 52 cout << data1[i] << " "; 53 cout << "}" << endl; 54 cout << "输入你要查找的目标:" << endl; 55 int dest; 56 cin >> dest; 57 cout <<"----------------------------------------"<< endl; 58 int index = BinarySearch(data1, 0, len - 1, dest,true); 59 #endif 60 #if 1 61 cout << "请参照下列数字:" << endl; 62 cout << "{"; 63 int len = sizeof(data2) / sizeof(int); 64 for (int i = 0; i < len; i++) 65 cout << data2[i] << " "; 66 cout << "}" << endl; 67 cout << "输入你要查找的目标:" << endl; 68 int dest; 69 cin >> dest; 70 cout << "----------------------------------------" << endl; 71 int index = BinarySearch(data2, 0, len - 1, dest, false); 72 #endif 73 if (index!=-1) 74 cout << dest << "在数组中的位置为第" << index << "个" << endl; 75 return 0; 76 77 }
运行结果:
(1)升序的情况:
(2)降序的情况:
相关文章
- 测试次数--蓝桥杯
- appium在爬虫中的应用--转
- [Javascript] let doesn't hoist -- false
- PYTHON--定期监测服务器端口,并将结果写入MYSQL
- 前端学习 -- Css -- overflow
- [AWS] IAM -- create user and attach policy
- Spring读源码系列之AOP--09---aop源码流程一把拿下
- Atitit 提升科技影响力----软件方面的.docx 目录 1. 大原则2 1.1. 科技强人必须是创新型[2 1.2. 要有一定的体量和规模2 1.3. 产业链齐全 底层基础 --高层应
- WnvHtmlToPdf-x64-v16.0--Crack
- 深入理解 C 指针阅读笔记 -- 第五章
- 23.第七章 Linux文件查找和打包压缩 -- 文件查找(一)
- k50.第十九章 K8s运维篇-集群升级 -- kubeadm v1.21 安装方式升级(一)
- vue--三种组件中之间的传值
- 服务器配置 iis 上传图片--HTTP 错误 401.3