基本概念:二分查找又称折半查找,要求待查找数组有序;优点是比较次数少,查找速度快;其缺点是要求待查表为有序表。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。
基本思想:首先假设已排序好的序列是升序,将要查找的元素与序列中间的元素比较,若相等,则查找成功;若待查找元素比中间元素大,则查找除去中间元素的后半部分序列,反之,则查找去除中间元素的前半部分序列,直到查到相同的元素或者所查找的序列范围为空为止。
实现思路:还是假设数组元素是升序的,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的value作比较,如果value=a[n/2]则找到value,算法终止。如 果value<a[n/2],则我们只要在数组a的左半部继续查找value。如果value>a[n/2],则我们只要在数组a的右半部继续查找value。
性能分析:若数组长度为n,则算法复杂度为O(log n)
具体代码:(非递归版)
public class binarySearchTest {
public static int binarySearch(int[] a,int value)
{
//若数组为空,则返回-1
if(a.length == 0 )
{
return -1;
}
int low = 0;
int high = a.length - 1;
while(low <= high)
{
int mid = (low + high) / 2;//这个是有BUG的
//打印中间元素选取过程,只是显示过程,与算法本身无关
for(int i = 0;i < a.length;i++)
{
System.out.print(a[i]);
if(i == mid)
{
System.out.print("#");//用#号表示中间元素
}
System.out.print(" ");//各个元素用空格隔开
}
System.out.println();//每次选取过程换行
//核心
if(value == a[mid])
{
return mid;
}
else if(value > a[mid])
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1; //不存在该元素则返回-1
}
public static void main(String[] args) {
int[] a={1,3,4,5,8,7,9,11,15};
System.out.println(binarySearch(a,9));
}
}
具体代码:(递归版)
public class binarySearchRecursionTest {
public static int binarySearchRecursion(int[] a,int fromIndex,int toIndex,int key)
{
if(fromIndex > toIndex) return -1;
int midIndex = (fromIndex + toIndex) / 2;//这个是有BUG的
int midVal = a[midIndex];
if(midVal > key)
{
return binarySearchRecursion(a,fromIndex,midIndex - 1,key);
}
else if(midVal <key)
{
return binarySearchRecursion(a, midIndex + 1, toIndex, key);
}
else
{
return midIndex;
}
}
public static void main(String[] args) {
int[] a={1,3,4,5,8,7,9,11,15};
System.out.println(binarySearchRecursion(a,0,a.length,9));
}
}
代码分析:
早前的jdk中Arrays类中的二分查找存在一个临界值的bug,bug在代码中的int mid = (low + high) / 2;当low + high大于正int范围时就会溢出,会抛出ArrayIndexOutOfBoundsException 异常。
解决办法:将int mid = (low + high) / 2修改为
int mid = low + ((high - low) / 2);
或者 int mid = (low + high) >>> 1;(最新的java.util.Arrays中用的是这个办法)
分享到:
相关推荐
Java二分查找递归算法
java二分查找算法,用于普通的代码算法。。,。。
本代码是利用java语言实现基本数据查询功能,实现算法为二分查找法
在这个教程中,我们将深入研究二分查找算法的工作原理,并提供一个Java示例来演示如何实现它。无论您是初学者还是有经验的Java开发者,通过学习这个算法,您将获得一个强大的搜索工具,有助于在大型有序数据集中快速...
Java 二分查找算法的示例代码。 欢迎访问个人博客。 http://blog.csdn.net/evanwang1987
该工具包含有Java一些比较常见的排序算法和查找算法。 排序算法包括:冒泡排序、选择排序 、插入排序、希尔排序、快速排序、归并排序、基数...查找算法包括:线性查找、二分查找、插值查询、斐波那契(黄金分割法)、
分别用递归和非递归方法实现二分查找算法 的完整程序,indexof()返回的是循环实现的二分法查找,getindex()实现的是递归算法实现的二分法查找。
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){ ...
多种排序查找算法的java实现源码,包括选择排序,冒泡排序,改进版冒泡排序,二分查找,归并排序等等
Java 二分查找算法的示例代码。 欢迎访问个人博客。 http://blog.csdn.net/evanwang1987
主要介绍了Java实现二分查找算法,实例分析了二分查找算法的原理与相关实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下
所谓的二分查找,指的是将待查的数据序列而分化,然后对比中间中间值和要查找值,判断结果,相等则找到,小于则在左边的子序列找,大于则在右边的子序列找
递归二分查找算法;
Tcp服务端与客户端的JAVA实例源代码,一个简单的Java TCP服务器端程序,别外还有一个客户端的程序,两者互相配合可以开发出超多的网络程序,这是最基础的部分。 递归遍历矩阵 1个目标文件,简单! 多人聊天室 3...
Java实现二分查找的递归和非递归算法
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
深入浅出,描述java算法,从0到1。...二分查找 O(logN) 无序数组的插入 O(1) 有序数组的插入 O(N) 无序数组的删除 O(N) 有序数组的删除 O(N) O(1)是最优秀的,O(logN)良好,O(N)还可以,O(N2)稍差(在冒泡法中见到)
基于java语言的二分查找,递归以及非递归算法,仅供学习娱乐
示例代码展示了如何使用二分查找在已排序的数组中找到目标元素的索引。 在代码中,我们定义了一个 binarySearch 方法,它接受一个已排序的整型数组 arr 和一个目标值 target 作为输入,并返回目标值在数组中的索引...