从来没有认真学过数据结构,也没写过什么像样的算法,注定我的程序员之路走的很艰辛,是该改变的时候,所以,接下来的时间里会从最基础开始学起,每天一点一点的积累,希望能有所收获,加油,为自己加油。
二分法查找
这个方法最常用于猜数字游戏中,比如同伴预先指定一个1~100之间的数字,要你去猜这个数字是多少,当你猜一个数字之后,你的同伴会告诉你这个数字是大了还是小了或者说猜对了,如果你采用乱蒙的方式,或者采用线性查找的方式,也许你运气很好,会一次或者两次猜中,但是如果运气很差的话就不能保证了。而采用二分法查找的方式猜1~100之间的数字,你最多猜7次就能完成,这就是二分法的优势,具体的代码实现如下。
public int myFind(int searchKey){
int min = 0;
int max = nElems - 1;//nElems 数组的长度
int current ;
while(true){
current = (min + max)/2;
//a为 int[] 数组
if(a[current] == searchKey){
return current; //返回当前的下标值
}else if(min>max){
return nElems; //如果min大于了max证明没有查找到,则返回数组长度
}else if(a[current] >searchKey){
max = current-1;
}else if(a[current] <searchKey){
min = current+1;
}
}
}
当然这样做的前提是该数组是有序数组,如果没有经过排序的数组这样操作,结果是可想而知的。
另外有序数组采用二分法查询效率很高,但是删除插入很慢,因为要删除和插入会使删除和插入数据的后面需要移动。
再另:二分法在数组长度较短的时候可能体现不出优势,但是当数组长度越长的时候他的优势越明显。比如0~1000,如果是线性查找的话是500次,而二分法查找则最多只需要10次。10000是14次,100000是17次……至于这最多次数是怎么算出来的,大家可以想想我们怎么查找的。我们是按2的n次幂进行查找的,2的7次幂是128,2的10次幂是1024……。OK,现在大家应该明白二分法查找的效率在数组长度越长的时候的效率越高的原因了吧,嘿嘿,抛砖引玉
再再另:数组的缺点:大小在初始化的时候就固定了,如果数据没有超过数组的大小,则出现空间浪费,如果超过了又会内存溢出;有序数组查询快速,但插入和删除又慢;无序数组插入快,但查找慢,这些都是数组的一些缺点。
看了的觉得很小儿科的请手下留情,如有不足请指正,谢谢
(参考《Java数据结构和算法》)
分享到:
相关推荐
二分法查找 *进行二分法查找的前提是数组已有序 *查找范围的上下界
写出二分法查找算法函数实现。
Java常用高效8大排序算法与二分法查找,适合正在学习算法和准备学习算法的算法爱好者和研究使用算法的开发人员使用。
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找 Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找
c 二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法...
此程序可实现二分查找算法,采用的是C编程。
C语言实现的二分法快速查找|二分法排序|二分法查找C#
二分法查找法
欢迎下载,资源共享。c语言实现。排序方法
class binary_search { public: int * arr; int nElems; public : binary_search(); binary_search(int max); virtual ~binary_search(); int find(int searchKey); void insert(int value);...
二分法查找算法.doc
——二分法查找 目录 课程导入 1 清楚并牢记二分法的实现条件 2 理解二分法的实现思路 3 读懂二分法的实现代码 数组的查找——二分法查找 也称拆半查找法,是一种高效的查找方法,前提条件是数组元素必须已经按升序...
易语言有序二分法查找源码,有序二分法查找,算法_二分法
九章算法之二分法(Binary Search) 适合找工作的小伙伴
初学java的基础算法,巩固学习,面试常考的基础算法,自己面试被问了几次,所以总结出来给大家分享!!!!
使用二分法查找的MATLAB程序编写,方便刚接触MATLAB的同学分享学习。
C#二分法快速查找查找连续数字,C#二分法快速查找查找连续数字,C#二分法快速查找查找连续数字,C#二分法快速查找查找连续数字,
二分法查找 (源码 C Java)
二分法查找是一种常用的查找算法,也称为折半查找。它适用于有序数组中查找某个元素的位置。二分法查找的思路是将数组分成两部分,每次查找都将待查找区间缩小一半,直到找到目标元素或者待查找区间为空为止。 ...
给定的表中用二分法查找指定数 给定的表中用二分法查找指定数 给定的表中用二分法查找指定数