溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
java 二分法詳解幾種方法
二分查找(java實現(xiàn))
二分查找
算法思想：又叫折半查找，要求待查找的序列有序。每次取中間位置的值與待查關鍵字比較，如果中間位置的值比待查關鍵字大，則在前半部分循環(huán)這個查找的過程，如果中間位置的值比待查關鍵字小，則在后半部分循環(huán)這個查找的過程。直到查找到了為止，否則序列中沒有待查的關鍵字。
實現(xiàn)：
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.遞歸實現(xiàn)
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)
查找第一個元素出現(xiàn)的位置（元素允許重復）
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;
}
}
查詢元素最后一次出現(xiàn)的位置
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;
}
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權內容。
