恩,昨天弄了哈二分查找,先来回忆一下二分查找的重要的知识点
1.有序的数组才能使用二分查找
2.二分查找法的效率很高,2的对数来得到二分法的查找次数。
3.二分查找法的原理
从一个有序数组中查找一个值,首先得到该数组的长度一半的(也就是得到该有序数组的中间值)的值,跟要查找的值进行比较,如果该值等于要查找的值,那么就结束了,如果该值大于要查找的值,那么我们的查找范围缩小,也就是说,这时我们要把我们查找的最大的的下标的值设置成为刚得到的下标。反之,我们则把最小的下标设置成为刚得到的下标值。按照这样的循环方式,最后查找到要查找的值,如果该数组中确实不存在该值,最后我们的最小下标会大于最大下标。此时查找就应该结束了。
核心代码如下:
while(true){
current = (min + max)/2;
if(a[current] == searchKey){
return current;
}else if(min>max){
return nElems;
}else if(a[current] >searchKey){
max = current-1;
}else if(a[current] <searchKey){
min = current+1;
}
}
上面说到的是二分查找法,二分查找法执行的一个前提是,有序数组,那么我们现在要说的就是怎么让一个数组变得有序起来—排序。
排序有多种,下面慢慢道来。
一:冒泡排序—最简单,但应该是最慢的排序
实现代码:
for(int out = a.length-1; out>1 ; out--){//排完一次,确定一个最大值,之后就少排一次
for(int in = 0 ; in < out; in++){//循环比较内层,根据外层比较的长度变小,相应的内层比较次数变少
if(a[in]>a[in+1]){
int temp = a[in];
a[in] = a[in+1];
a[in+1] = temp;
}
}
}
从上面可以看到,如果是10个的数据的数组,他的比较次数应该是:9+8+7+……+1=45
也即:(N-1)+(N-2)+……+1=N*(N-1)/2。效率可想而知。
(未完待续)
分享到:
相关推荐
高二数学必修3第一章算法初步知识点:秦九韶算法与排序.docx
数据结构课程设计_排序算法集成 掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力 2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能 3. 提高综合运用所学的理论知识和方法...
使用排序算法解决实际问题,初步体会文件的输入输出
封装完整的内排序算法,对初步学习编程者很有帮助
通过排序算法的设计,培养学生综合利用C语言版数据结构进行程序设计的能力,加强函数的运用及学生对软件工程方法的初步认识,提高软件系统分析能力和程序文档建立、归纳总结的能力,掌握排序算法,使学生能够解决...
论文研究-计算层次分析法中排序权值的加速遗传算法.pdf, 为处理 AHP中判断矩阵的一致性问题 ,直接从判断矩阵的定义出发 ,提出用加速遗传算法同时计算 AHP中各要素的排序...
算法以英语和伪代码的形式描述,具备初步程序设计经验的人就能看懂;说明和解释力求浅显易懂,不失深度和数学严谨性。 --------------------------------------------------------------- 目录 Introduction to ...
算法以英语和伪代码的形式描述 具备初步程序设计经验的人就能看懂;说明和解释力求浅显易懂 不失深度和数学严谨性 《算法导论 原书第3版 》选材经典 内容丰富 结构合理 逻辑清晰 对本科生的数据结构课程和研究生的...
1.1 建立算法初步概念 1.1.1 什么是算法 1.1.2 算法的发展历史 1.1.3 算法的分类 1.2 算法相关概念的区别 1.2.1 算法与公式的关系 1.2.2 算法与程序的关系 1.2.3 算法与数据结构的关系 1.3 算法的表示 1.3.1 自然...
算法以英语和伪代码的形式描述,具备初步程序设计经验的人就能看懂;说明和解释力求浅显易懂,不失深度和数学严谨性。全书选材经典、内容丰富、结构合理、逻辑清晰,对本科生的数据结构课程和研究生的算法课程都是...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
算法以英语和伪代码的形式描述,具备初步程序设计经验的人就能看懂;说明和解释力求浅显易懂,不失深度和数学严谨性。 全书选材经典、内容丰富、结构合理、逻辑清晰,对本科生的数据结构课程和研究生的算法课程都是...
算法以英语和伪代码的形式描述,具备初步程序设计经验的人就能看懂;说明和解释力求浅显易懂,不失深度和数学严谨性。 《算法导论(原书第3版)》选材经典、内容丰富、结构合理、逻辑清晰,对本科生的数据结构课程和...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。《算法导论(原书第2版...
C++ 插入算法适合初学者用于初步学习算法思想算法的敲门砖
算法以英语和伪代码的形式描述,具备初步程序设计经验的人就能看懂;说明和解释力求浅显易懂,不失深度和数学严谨性。 全书选材经典、内容丰富、结构合理、逻辑清晰,对本科生的数据结构课程和研究生的算法课程都是...
A*路径寻找算法入门 初步:搜索区域 开始搜索 路径排序 ...
算法以英语和伪代码的形式描述,具备初步程序设计经验的人就能看懂;说明和解释力求浅显易懂,不失深度和数学严谨性。全书选材经典、内容丰富、结构合理、逻辑清晰,对本科生的数据结构课程和研究生的算法课程都是...