二分查找
算法思想:又叫折半查找,要求待查找的序列有序。每次取中间位置的值与待查关键字比较,如果中间位置的值比待查关键字大,则在前半部分循环这个查找的过程,如果中间位置的值比待查关键字小,则在后半部分循环这个查找的过程。直到查找到了为止,否则序列中没有待查的关键字。
实现:
1.非递归代码
public static int biSearch(int []array,int a){ int lo=0; int hi=array.length-1; int mid; while(lo<=hi){ mid=(lo+hi)/2; if(array[mid]==a){ return mid+1; }else if(array[mid]<a){ lo=mid+1; }else{ hi=mid-1; } } return -1; }
2.递归实现
public static int sort(int []array,int a,int lo,int hi){ if(lo<=hi){ int mid=(lo+hi)/2; if(a==array[mid]){ return mid+1; } else if(a>array[mid]){ return sort(array,a,mid+1,hi); }else{ return sort(array,a,lo,mid-1); } } return -1; }
时间复杂度为 O(logN)
查找第一个元素出现的位置(元素允许重复)
public static int biSearch(int []array,int a){ int n=array.length; int low=0; int hi=n-1; int mid=0; while(low<hi){ mid=(low+hi)/2; if(array[mid]<a){ low=mid+1; }else{ hi=mid; } } if(array[low]!=a){ return -1; }else{ return low; } }
查询元素最后一次出现的位置
public static int biSearch(int []array,int a){ int n=array.length; int low=0; int hi=n-1; int mid=0; while(low<hi){ mid=(low+hi+1)/2; if(array[mid]<=a){ low=mid; }else{ hi=mid-1; } } if(array[low]!=a){ return -1; }else{ return hi; } }
相关推荐
二分查找的三种实现方式 分别是: 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实现
用java二分查找法实现日期搜索 用java二分查找法实现日期搜索 用java二分查找法实现日期搜索
java实现二分查找,包含时间复杂度的计算
用java实现二分查找法BianrySearch 用java实现二分查找法BianrySearch 用java实现二分查找法BianrySearch
java二分查找开发技术实现代码,注意二分查找必须是有序数组
java 二分查找法的实现方法 java 二分查找法的实现方法
JAVA用递归和非递归的方法实现二分查找
用java实现了二分查找,效率较高,思路清晰易懂。
Java二分查找递归算法
二分查找的递归与非递归实现(java版)
java二分查找算法,用于普通的代码算法。。,。。
在这个教程中,我们将深入研究二分查找算法的工作原理,并提供一个Java示例来演示如何实现它。无论您是初学者还是有经验的Java开发者,通过学习这个算法,您将获得一个强大的搜索工具,有助于在大型有序数据集中快速...
Java 二分查找算法的示例代码。 欢迎访问个人博客。 http://blog.csdn.net/evanwang1987
C和Java的二分查找代码实现
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