java 二分法詳解幾種實(shí)現(xiàn)方法
更新時(shí)間：2017年02月25日 10:50:49 投稿：lqh
這篇文章主要介紹了java 二分法詳解幾種方法的相關(guān)資料,需要的朋友可以參考下
java 二分法詳解幾種方法
二分查找(java實(shí)現(xiàn))
二分查找
算法思想：又叫折半查找，要求待查找的序列有序。每次取中間位置的值與待查關(guān)鍵字比較，如果中間位置的值比待查關(guān)鍵字大，則在前半部分循環(huán)這個(gè)查找的過程，如果中間位置的值比待查關(guān)鍵字小，則在后半部分循環(huán)這個(gè)查找的過程。直到查找到了為止，否則序列中沒有待查的關(guān)鍵字。
實(shí)現(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.遞歸實(shí)現(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;
}
時(shí)間復(fù)雜度為 O(logN)
查找第一個(gè)元素出現(xiàn)的位置（元素允許重復(fù)）
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;
}
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
相關(guān)文章
Java中使用標(biāo)簽(label)來控制循環(huán)的執(zhí)行流程
java 和 label 兩個(gè)完全不相干的詞,今天我把他們連接在一起了,試想一個(gè)問題,雙循環(huán)在不使用 return 的情況下,如何停止外循環(huán)？所以本文給大家介紹了Java中使用標(biāo)簽(label)來控制循環(huán)的執(zhí)行流程,需要的朋友可以參考下2024-06-06
這篇文章主要介紹了Java中super和this關(guān)鍵字詳解，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-06-06
數(shù)組是相同類型數(shù)據(jù)的有序集合數(shù)組描述的是相同類型的若干個(gè)數(shù)據(jù),按照一定的先后次序排列組合而成。其中,每一個(gè)數(shù)據(jù)稱作一個(gè)數(shù)組元素,每個(gè)數(shù)組元素可以通過一個(gè)下標(biāo)來訪問它們數(shù)組的聲明創(chuàng)建2021-07-07
Java Builder Pattern建造者模式詳解及實(shí)例
這篇文章主要介紹了Java Builder Pattern建造者模式詳解及實(shí)例的相關(guān)資料,需要的朋友可以參考下2017-01-01
Spring Boot整合FTPClient線程池的實(shí)現(xiàn)示例
這篇文章主要介紹了Spring Boot整合FTPClient線程池的實(shí)現(xiàn)示例，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-12-12
數(shù)組存儲(chǔ)同一種數(shù)據(jù)類型多個(gè)元素的集合,既可以存儲(chǔ)基本數(shù)據(jù)類型,也可以存儲(chǔ)引用數(shù)據(jù)類型,這篇文章主要給大家介紹了關(guān)于JavaSE一維數(shù)組和二維數(shù)組用法的相關(guān)資料,需要的朋友可以參考下2024-04-04
MapStruct處理Java中實(shí)體與模型間不匹配屬性轉(zhuǎn)換的方法
今天小編就為大家分享一篇關(guān)于MapStruct處理Java中實(shí)體與模型間不匹配屬性轉(zhuǎn)換的方法，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2019-03-03
題目是：求1000！的結(jié)果末尾有多少個(gè)0,解題思路：兩個(gè)素?cái)?shù)2、5，相乘即可得到10，我們可以認(rèn)為，有多少組2、5，結(jié)尾就有多少個(gè)0，下面是代碼,需要的朋友可以參考下2014-02-02
使用@Value為靜態(tài)變量導(dǎo)入并使用導(dǎo)入的靜態(tài)變量進(jìn)行初始化方式
這篇文章主要介紹了使用@Value為靜態(tài)變量導(dǎo)入并使用導(dǎo)入的靜態(tài)變量進(jìn)行初始化方式，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-02-02
這篇文章主要介紹了Mybatis批量插入,返回主鍵ID不成功,巨坑記錄,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-12-12