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ò)程，如果中間位置的值比待查關(guān)鍵字小，則在后半部分循環(huán)這個(gè)查找的過(guò)程。直到查找到了為止，否則序列中沒(méi)有待查的關(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;
}
}
查詢?cè)刈詈笠淮纬霈F(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;
}
}
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
相關(guān)文章
這篇文章主要介紹了Maven生命周期和及插件原理用法詳解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值的相關(guān)資料2020-08-08
Springboot項(xiàng)目異常處理及返回結(jié)果統(tǒng)一
這篇文章主要介紹了Springboot項(xiàng)目異常處理及返回結(jié)果統(tǒng)一，文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的朋友可以參考一下2022-08-08
這篇文章主要介紹了Feign調(diào)用傳輸文件異常的解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-06-06
這篇文章主要介紹了通過(guò)IDEA快速定位和排除依賴沖突問(wèn)題，本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2019-06-06
這篇文章主要介紹了Java 動(dòng)態(tài)代理深入理解的相關(guān)資料,需要的朋友可以參考下2017-03-03
Apache Shrio安全框架實(shí)現(xiàn)原理及實(shí)例詳解
這篇文章主要介紹了Apache Shrio安全框架實(shí)現(xiàn)原理及實(shí)例詳解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-04-04
Java實(shí)現(xiàn)圖片轉(zhuǎn)換PDF文件的示例代碼
這篇文章主要介紹了Java實(shí)現(xiàn)圖片轉(zhuǎn)換PDF文件的示例代碼，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
這篇文章主要介紹了java仿QQ微信聊天室的實(shí)現(xiàn)代碼，代碼簡(jiǎn)單易懂，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，,需要的朋友可以參考下2021-04-04
詳解Java如何使用集合來(lái)實(shí)現(xiàn)一個(gè)客戶信息管理系統(tǒng)
讀萬(wàn)卷書(shū)不如行萬(wàn)里路，只學(xué)書(shū)上的理論是遠(yuǎn)遠(yuǎn)不夠的，只有在實(shí)戰(zhàn)中才能獲得能力的提升，本篇文章手把手帶你用Java 集合實(shí)現(xiàn)一個(gè)客戶信息管理系統(tǒng),大家可以在過(guò)程中查缺補(bǔ)漏，提升水平2021-11-11
SpringBoot啟動(dòng)流程SpringApplication準(zhǔn)備階段源碼分析
這篇文章主要為大家介紹了SpringBoot啟動(dòng)流程SpringApplication準(zhǔn)備階段源碼分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-04-04