Java實(shí)現(xiàn)二分查找算法實(shí)例分析
本文實(shí)例講述了Java實(shí)現(xiàn)二分查找算法。分享給大家供大家參考。具體如下：
1. 前提：二分查找的前提是需要查找的數(shù)組必須是已排序的，我們這里的實(shí)現(xiàn)默認(rèn)為升序
2. 原理：將數(shù)組分為三部分，依次是中值（所謂的中值就是數(shù)組中間位置的那個(gè)值）前，中值，中值后；將要查找的值和數(shù)組的中值進(jìn)行比較，若小于中值則在中值前面找，若大于中值則在中值后面找，等于中值時(shí)直接返回。然后依次是一個(gè)遞歸過程，將前半部分或者后半部分繼續(xù)分解為三部分?？赡苊枋龅貌皇呛芮宄?，若是不理解可以去網(wǎng)上找。從描述上就可以看出這個(gè)算法適合用遞歸來實(shí)現(xiàn)，可以用遞歸的都可以用循環(huán)來實(shí)現(xiàn)。所以我們的實(shí)現(xiàn)分為遞歸和循環(huán)兩種，可以根據(jù)代碼來理解算法
實(shí)現(xiàn)代碼：
public class BinarySearch {
public static void main(String[] args){
int searchArr[] = new int[1000000];
for(int i=0;i<1000000;i++){
searchArr[i]=i;
}
System.out.println(binSearch(searchArr,0,searchArr.length-1,99));
System.out.println(binSearch(searchArr,99));
}
//遞歸二分查找
public static int binSearch(int arr[], int start,int end,int sear){
int mid = (end-start)/2 + start;
if(sear==arr[mid]){
return mid;
}
if(start>=end){
return -1;
}else if(sear < arr[mid]){
return binSearch(arr,0,mid-1,sear);
}else if(sear >arr[mid]){
return binSearch(arr,mid+1,end,sear);
}
return -1;
}
//循環(huán)二分查找
public static int binSearch(int arr[],int key){
int mid = arr.length/2;
int start = 0;
int end = arr.length-1;
while(start<=end){
mid = (end-start)/2+start;
if(key ==arr[mid]){
return mid;
}else if(key <= arr[mid]){
end = mid-1;
}else if(key >=arr[mid]){
start = mid+1;
}
}
return -1;
}
效率比較：
循環(huán)二分查找算法的效率高于遞歸二分查找算法
希望本文所述對(duì)大家的java程序設(shè)計(jì)有所幫助。
相關(guān)文章
SpringBoot應(yīng)用啟動(dòng)內(nèi)置Tomcat的過程源碼分析
這篇文章主要介紹了SpringBoot應(yīng)用啟動(dòng)內(nèi)置Tomcat的過程分析,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-07-07
關(guān)于SpringBoot中的XA事務(wù)詳解
這篇文章主要介紹了關(guān)于SpringBoot中的XA事務(wù)詳解,事務(wù)管理可以確保數(shù)據(jù)的一致性和完整性，同時(shí)也可以避免數(shù)據(jù)丟失和沖突等問題。在分布式環(huán)境中，XA?事務(wù)是一種常用的事務(wù)管理方式,需要的朋友可以參考下2023-07-07
java如何判斷一個(gè)數(shù)是否是素?cái)?shù)(質(zhì)數(shù))
這篇文章主要介紹了java如何判斷一個(gè)數(shù)是否是素?cái)?shù)(質(zhì)數(shù))，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-09-09
Java注解的Retention和RetentionPolicy實(shí)例分析
這篇文章主要介紹了Java注解的Retention和RetentionPolicy,結(jié)合實(shí)例形式分析了Java注解Retention和RetentionPolicy的基本功能及使用方法,需要的朋友可以參考下2019-09-09
Spring中@ExceptionHandler注解的使用方式
這篇文章主要介紹了Spring中@ExceptionHandler注解的使用方式,@ExceptionHandler注解我們一般是用來自定義異常的,可以認(rèn)為它是一個(gè)異常攔截器(處理器),需要的朋友可以參考下2024-01-01
這篇文章主要為大家介紹了DoytoQuery中的查詢映射方案詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-12-12
這篇文章主要為大家詳細(xì)介紹了JavaMail郵件簡(jiǎn)介及API概述第一篇，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2016-12-12
Java遞歸讀取文件例子_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
本文通過一段示例代碼給大家介紹了java遞歸讀取文件的方法，代碼簡(jiǎn)單易懂，非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友參考下吧2017-05-05
這篇文章主要給大家介紹了關(guān)于String中intern方法的使用場(chǎng)景，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
Java異常處理操作 Throwable、Exception、Error
這篇文章主要介紹了Java異常處理操作 Throwable、Exception、Error，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-06-06