需求:在排好顺序的一串数字中,找到数字T
一般解法:从左到右扫描数据,其运行花费线性时间O(N)。然而这个算法并没有用到该表已经排序的事实。
/** * * @param array * 顺序数组 * @param t * 要查找对象 * @return */ public static <T extends Comparable<? super T>> int Search(T[] array, T t) { for (int i = 0; i < array.length; i++) {// 顺序比较 if (t.compareTo(array[i]) == 0) { return i; } } return -1; }
好的解法:验证T是否是居中的元素,如果是就找到了,如果小于(说明居中右侧数据都>T),那么可以用同样的策略于居中元素左侧已经排序的子序列,如果大于,同理。
/** * * @param array * 顺序数组 * @param t * 要查找对象 * @return */ public static <T extends Comparable<? super T>> int binarySearch(T[] array, T t) { int low = 0;// 下限 int high = array.length - 1; // 上限 while (low <= high) { int i = (low + high) / 2; if (t.compareTo(array[i]) > 0) { low = i + 1; // 重置下限 } else if (t.compareTo(array[i]) < 0) { high = i - 1;// 重置上限 } else { return i; } } return -1; }
折半查找提供了在O(logN)时间内的contains操作,但是所有其他操作均需要O(N)时间。
在数据是稳定(即不允许插入操作和删除操作)的应用中,这种操作可能是非常有用的。此时输入数据只需要一次排序,但是此后访问会很快。
大多数时候算法表达式的简明性是以速度的降低为代价的。
相关推荐
java二分查找开发技术实现代码,注意二分查找必须是有序数组
java 二分查找法的实现方法 java 二分查找法的实现方法
用java二分查找法实现日期搜索 用java二分查找法实现日期搜索 用java二分查找法实现日期搜索
Java 二分查找算法的示例代码。 欢迎访问个人博客。 http://blog.csdn.net/evanwang1987
Java 二分查找算法的示例代码。 欢迎访问个人博客。 http://blog.csdn.net/evanwang1987
Java二分查找递归算法
java二分查找算法,用于普通的代码算法。。,。。
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好,占用系统内存较少;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素...
Java二分查找.doc
用java实现二分查找法BianrySearch 用java实现二分查找法BianrySearch 用java实现二分查找法BianrySearch
java实现二分查找,包含时间复杂度的计算
JAVA用递归和非递归的方法实现二分查找
在这个教程中,我们将深入研究二分查找算法的工作原理,并提供一个Java示例来演示如何实现它。无论您是初学者还是有经验的Java开发者,通过学习这个算法,您将获得一个强大的搜索工具,有助于在大型有序数据集中快速...
二分查找的三种实现方式 分别是: while for 递归
while(low){ if(x==arr[mid]){ return mid; } else if(mid>0&&x[mid]){... else if(mid){//若前面没有判断,则当要查找数超过arr数组中最大值时出现死循环。 low=mid+1; mid=(low+high)/2; }
用java实现了二分查找,效率较高,思路清晰易懂。
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 要求: 必须采用顺序存储结构。 必须按关键字大小有序排列。...
将二分法查找和快速排序集合在JavaApplet中,其中快速排序给输出中间过程,适合初学者观看。有问题可以联系本人,欢迎。
简单地实现了二分查找的可视化。界面很简单就包括两个部分:界面左侧是可视化查找部分,右侧是二分查找的代码。 程序的关键点主要有两点: 1. 如何在页面上表示出查找程序的运行过程。 2. 如何将排序程序的运行...
public class 二分查找 { 二分查找(int N,int M,int[]a){ int min = 0, max = 0,mid,temp; for(int i=0;i;i++){ if(min[i]) min=a[i]; max+=a[i]; } mid=(min+max)/2; temp=test(N,mid,a); while(min){ ...