Java實現(xiàn)二分查找算法實例分析
更新時間：2015年07月29日 17:48:45 作者：tolcf
這篇文章主要介紹了Java實現(xiàn)二分查找算法,實例分析了二分查找算法的原理與相關實現(xiàn)技巧,具有一定參考借鑒價值,需要的朋友可以參考下
本文實例講述了Java實現(xiàn)二分查找算法。分享給大家供大家參考。具體如下：
1. 前提：二分查找的前提是需要查找的數(shù)組必須是已排序的，我們這里的實現(xiàn)默認為升序
2. 原理：將數(shù)組分為三部分，依次是中值（所謂的中值就是數(shù)組中間位置的那個值）前，中值，中值后；將要查找的值和數(shù)組的中值進行比較，若小于中值則在中值前面找，若大于中值則在中值后面找，等于中值時直接返回。然后依次是一個遞歸過程，將前半部分或者后半部分繼續(xù)分解為三部分?？赡苊枋龅貌皇呛芮宄羰遣焕斫饪梢匀ゾW(wǎng)上找。從描述上就可以看出這個算法適合用遞歸來實現(xiàn)，可以用遞歸的都可以用循環(huán)來實現(xiàn)。所以我們的實現(xiàn)分為遞歸和循環(huán)兩種，可以根據(jù)代碼來理解算法
實現(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)二分查找算法的效率高于遞歸二分查找算法
希望本文所述對大家的java程序設計有所幫助。
相關文章
Java BeanPostProcessor與BeanFactoryPostProcessor基礎使用講解
這篇文章主要介紹了Java BeanPostProcessor與BeanFactoryPostProcessor基礎使用，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習吧2022-11-11
這篇文章主要為大家詳細介紹了SpringMVC的自定義異常類，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要為大家介紹了Java C++題解leetcode816模糊坐標示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-01-01
這篇文章主要介紹了Java使用Condition控制線程通信的方法,結(jié)合實例形式分析了使用Condition類同步檢測控制線程通信的相關操作技巧,需要的朋友可以參考下2019-09-09
這篇文章主要為大家介紹了20秒教你學會List函數(shù)排序操作示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-09-09
這篇文章主要介紹了Java基本數(shù)據(jù)類型和運算符,結(jié)合實例形式詳細分析了java基本數(shù)據(jù)類型、數(shù)據(jù)類型轉(zhuǎn)換、算術運算符、邏輯運算符等相關原理與操作技巧,需要的朋友可以參考下2021-09-09
SpringBoot?AOP?@Pointcut切入點表達式排除某些類方式
這篇文章主要介紹了SpringBoot?AOP?@Pointcut切入點表達式排除某些類方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-11-11
這篇文章主要介紹了Java中int和Integer的區(qū)別文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-04-04
這篇文章主要介紹了Java 多個異常共享同一個異常處理器的方法,Java 的異常處理機制，在 Java 7 中有了非常大的改進。其中一個特性就是，支持多個異常共享同一個異常處理器。,需要的朋友可以參考下2019-06-06
這篇文章主要介紹了Java?IPage分頁加自定義sql,主要包括引入依賴，impl常規(guī)操作，本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-06-06