二 分查找是一种高效率线性表的查找算法。在查找时必须将线性表中的关键字排好序。基本思路是:先确定线性表的中间位置 mid=(first+last)/2;比较所要查找的关键字 key与中间位置的关键字的大小,如果比key和mid.key相等则返回; key比mid.key大(假定为升序)这所要查找的关键字在mid和last之间;否则在first与mid之间。继续按照上面方法查找中间元素,直到 找到为止。
具体实现如下
public class BinarySearch {
public BinarySearch() {
super();
}
/**
* Java二分法查找
* @param a
* @param key
* @return
*/
public static int binarySearch(int[] a, int key) {
if(a.length==0)
return -1;
//开始位置
int first = 0;
//结束位置
int last = a.length-1;
//中间位置
int mid;
//如果开始时,小于则结束.
while(first<=last)
{
mid = (first+last)/2;
//如果等于key,返回这个数在数组中的位置.
if(a[mid]==key)
return mid;
//如果大于key,则在左边.
if(a[mid]>key)
last = mid-1;
//如果小于key,则在右边
if(a[mid]<key)
first = mid+1;
}
return -1;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a={1,3,4,5,8,7,9,11,15};
System.out.println(binarySearch(a,9));
}
}
这样就打印出了所要查找的关键字所在位置的下标。对二分查找求平均查找长度二分查找的过程相当与一棵二叉排序树,所以总节点数为n=2^h- 1,h=Log2 (n+1)。 第i层上的节点数为2^(1-1);在等概率的情况下,平均查找长度ASL=Log2 (n+1)-1。
分享到:
相关推荐
java 二分法查找案例与数组排序案例
二分法查找 *进行二分法查找的前提是数组已有序 *查找范围的上下界
二分法查找是一种常用的查找算法,也称为折半查找。它适用于有序数组中查找某个元素的位置。二分法查找的思路是将数组分成两部分,每次查找都将待查找区间缩小一半,直到找到目标元素或者待查找区间为空为止。 ...
主要介绍了Java二分法查找的相关资料,需要的朋友可以参考下
主要为大家详细介绍了java实现二分法查找出数组重复数字,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
——二分法查找 目录 课程导入 1 清楚并牢记二分法的实现条件 2 理解二分法的实现思路 3 读懂二分法的实现代码 数组的查找——二分法查找 也称拆半查找法,是一种高效的查找方法,前提条件是数组元素必须已经按升序...
二分法查找 (源码 C Java)
冒泡排序、快速排序和二分法查找的分析 Java
写出二分法查找算法函数实现。
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找 Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找
初学java的基础算法,巩固学习,面试常考的基础算法,自己面试被问了几次,所以总结出来给大家分享!!!!
Java常用高效8大排序算法与二分法查找,适合正在学习算法和准备学习算法的算法爱好者和研究使用算法的开发人员使用。
JAVA 数据结构二分法查找代码。(实验)
主要介绍了Java使用二分法进行查找和排序的示例,二分插入排序和二分查找是基础的算法,需要的朋友可以参考下
主要介绍了java 中二分法查找的应用实例的相关资料,希望通过本文大家能掌握二分法的使用方法,需要的朋友可以参考下
主要介绍了java 二分法算法的实例的相关资料,希望通过本文大家能够掌握二分法,需要的朋友可以参考下
java 二分查找法的实现方法 java 二分查找法的实现方法
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找(同步到博客).doc
文章目录6.4 冒泡排序的基础算法6.4.1 冒泡排序优化算法6.5二分法查找(折半检索) 6.4 冒泡排序的基础算法 冒泡排序是常用的排序算法,笔试中非常常见。 算法重复地走访过排序的数列,一次比较两个元素,如果他们的...