java 二分法詳解幾種實現(xiàn)方法
更新時間：2017年02月25日 10:50:49 投稿：lqh
這篇文章主要介紹了java 二分法詳解幾種方法的相關(guān)資料,需要的朋友可以參考下
java 二分法詳解幾種方法
二分查找(java實現(xiàn))
二分查找
算法思想：又叫折半查找，要求待查找的序列有序。每次取中間位置的值與待查關(guān)鍵字比較，如果中間位置的值比待查關(guān)鍵字大，則在前半部分循環(huán)這個查找的過程，如果中間位置的值比待查關(guān)鍵字小，則在后半部分循環(huán)這個查找的過程。直到查找到了為止，否則序列中沒有待查的關(guā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;
}
時間復(fù)雜度為 O(logN)
查找第一個元素出現(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)文章
這篇文章主要介紹了Maven生命周期和及插件原理用法詳解,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值的相關(guān)資料2020-08-08
Springboot項目異常處理及返回結(jié)果統(tǒng)一
這篇文章主要介紹了Springboot項目異常處理及返回結(jié)果統(tǒng)一，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的朋友可以參考一下2022-08-08
這篇文章主要介紹了Feign調(diào)用傳輸文件異常的解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-06-06
這篇文章主要介紹了通過IDEA快速定位和排除依賴沖突問題，本文給大家介紹的非常詳細，具有一定的參考借鑒價值,需要的朋友可以參考下2019-06-06
這篇文章主要介紹了Java 動態(tài)代理深入理解的相關(guān)資料,需要的朋友可以參考下2017-03-03
Apache Shrio安全框架實現(xiàn)原理及實例詳解
這篇文章主要介紹了Apache Shrio安全框架實現(xiàn)原理及實例詳解,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-04-04
Java實現(xiàn)圖片轉(zhuǎn)換PDF文件的示例代碼
這篇文章主要介紹了Java實現(xiàn)圖片轉(zhuǎn)換PDF文件的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
這篇文章主要介紹了java仿QQ微信聊天室的實現(xiàn)代碼，代碼簡單易懂，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，,需要的朋友可以參考下2021-04-04
詳解Java如何使用集合來實現(xiàn)一個客戶信息管理系統(tǒng)
讀萬卷書不如行萬里路，只學(xué)書上的理論是遠遠不夠的，只有在實戰(zhàn)中才能獲得能力的提升，本篇文章手把手帶你用Java 集合實現(xiàn)一個客戶信息管理系統(tǒng),大家可以在過程中查缺補漏，提升水平2021-11-11
SpringBoot啟動流程SpringApplication準備階段源碼分析
這篇文章主要為大家介紹了SpringBoot啟動流程SpringApplication準備階段源碼分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-04-04