Java 二分法检索算法代码实现详解
一，二分法检索算法介绍
二分法检索（binarysearch）又称折半检索，二分法检索的基本思想是设字典中的元素从小到大有序地存放在数组（array）中。是最常用的搜索算法之一，这主要是由于其搜索时间短。
二，二分法检索算法思路
这种搜索使用分而治之方法，并且需要事先对数据集进行排序。
它将输入集合分为相等的两半，并且每次迭代都将目标元素与中间元素进行比较。
如果找到该元素，则搜索结束。否则，我们根据目标元素是小于还是大于中间元素，通过划分并选择适当的数组分区来继续寻找元素。
这就是为什么对BinarySearch有一个排序的集合很重要的原因。
当firstIndex（我们的指针）经过lastIndex（最后一个元素）时，搜索将终止，这意味着我们已经搜索了整个数组，并且该元素不存在。
有两种方法可以实现此算法- 迭代和递归。
这里不应该是关于时间和空间这两个实现之间复杂的差异，虽然这不成立于所有语言。
三，二分法检索算法代码实现
迭代式
首先让我们看一下迭代方法：
publicclassSearchAlgorithms{
/**
*迭代方法
*@paramarr
*@paramelementToSearch
*@return
*/
publicstaticintbinarySearch(intarr[],intelementToSearch){
intfirstIndex=0;
intlastIndex=arr.length-1;
//终止条件(元素不存在)
while(firstIndex<=lastIndex){
intmiddleIndex=(firstIndex+lastIndex)/2;
//如果中间元素是我们的目标元素，那么返回它的索引
if(arr[middleIndex]==elementToSearch){
returnmiddleIndex;
}
//如果中间的元素比较小
//将我们的指数指向中间+1，不考虑前半部分
elseif(arr[middleIndex]elementToSearch)
lastIndex=middleIndex-1;
}
return-1;
}
/**
*用于打印结果
*@paramtargetParameter
*@paramindex
*/
publicstaticvoidprint(inttargetParameter,intindex){
if(index==-1){
System.out.println(targetParameter+"未找到");
}
else{
System.out.println(targetParameter+"搜索结果为:"+index);
}
}
//测试一下
publicstaticvoidmain(String[]args){
intindex=binarySearch(newint[]{89,57,91,47,95,3,27,22,67,99},67);
print(67,index);
}
}
输出：
递归的
现在让我们看一下递归实现：
递归方法的区别在于，一旦获得新分区，我们便会调用方法本身。在迭代方法中，每当确定新分区时，我们都会修改第一个和最后一个元素，并在同一循环中重复该过程。
这里的另一个区别是递归调用被推入方法调用堆栈，并且每个递归调用占用一个空间单位。
我们可以像这样使用这种算法：
publicclassSearchAlgorithms{
/**
*递归方法
*@paramarr
*@paramelementToSearch
*@return
*/
publicstaticintrecursiveBinarySearch(intarr[],intfirstElement,intlastElement,intelementToSearch){
//结束条件
if(lastElement>=firstElement){
intmid=firstElement+(lastElement-firstElement)/2;
//如果中间元素是我们的目标元素，那么返回它的索引
if(arr[mid]==elementToSearch)
returnmid;
//如果中间元素大于目标元素
if(arr[mid]>elementToSearch)
returnrecursiveBinarySearch(arr,firstElement,mid-1,elementToSearch);
returnrecursiveBinarySearch(arr,mid+1,lastElement,elementToSearch);
}
return-1;
}
/**
*用于打印结果
*@paramtargetParameter
*@paramindex
*/
publicstaticvoidprint(inttargetParameter,intindex){
if(index==-1){
System.out.println(targetParameter+"未找到");
}
else{
System.out.println(targetParameter+"搜索结果为:"+index);
}
}
//测试一下
publicstaticvoidmain(String[]args){
intindex=recursiveBinarySearch(newint[]{3,22,27,47,57,67,89,91,95,99},0,10,67);
print(67,index);
}
}
输出：
四，以算法时间复杂度和空间复杂度总结算法。
时间复杂度
由于二进制搜索每次将其时间复杂度为O（log（N））时都会将数组分为两半。此时间复杂度是线性搜索O（N）时间复杂度的显着改进。
空间复杂度
此搜索仅需要一个空间单位即可存储要搜索的元素。因此，其空间复杂度为O（1）。
如果二分法检索是递归实现的，则需要将对该方法的调用存储在堆栈中。在最坏的情况下，这可能需要O（log（N））空间。
它是大多数用于搜索的库中最常用的搜索算法，二分法检索树也被许多存储排序数据的数据结构所使用。
该Arrays.binarySearch方法中的JavaAPI也实现了二进制搜索哦。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。