首頁 > Java > java教程 > Java的二分查找實作原理及程式碼實現

Java的二分查找實作原理及程式碼實現

王林
發布: 2023-04-27 08:52:06
轉載
1105 人瀏覽過

1.二分查找步驟描述

(1)先確定整個查找區間的中間位置 mid = ( left right )/ 2

(2)用將關鍵字值與中間位置的關鍵字值比較;

若相等,則查找成功

#若大於,則在後(右)半個區域繼續進行折半查找

若小於,則在前(左)半個區域繼續進行折半查找

(3)對確定的縮小區域再按折半公式,重複上述步驟。

最後,得到結果:要嘛找成功, 要嘛找失敗。折半查找的儲存結構採用一維數組存放。折半查找演算法舉例

Java的二分查找實作原理及程式碼實現2.要求

(1)必須採用順序儲存結構。

(2)必須依關鍵字大小有序排列。

3.實例

public class Demo {
 
    public static void main(String[] args) {
        int[] arr={-1,0,3,5,9,12};//查找的数组
        int searchNum=13;//查找的目标数
        Arrays.sort(arr);
 
        int resultOne=binarySearchOne(arr,searchNum,0,arr.length-1);
        System.out.println(resultOne);
 
        int resultTwo=binarySearchTwo(arr,searchNum);
        System.out.println(resultTwo);
    }
 
    /**
     * 递归实现
     * @param arr
     * @param searchNum
     * @param start
     * @param end
     * @return
     */
    public static int binarySearchOne(int[] arr,int searchNum,int start,int end){
        if(start>end)
            return -1;
        int middle=(start+end)/2;
        if(searchNum<arr>arr[middle])
            return binarySearchOne(arr,searchNum,middle+1,end);
        else
            return middle;
    }
 
    /**
     * 非递归实现
     * @param arr
     * @param searchNum
     * @return
     */
    private static int binarySearchTwo(int[] arr, int searchNum) {
        int start=0;
        int end=arr.length-1;
        while(startarr[middle])
                start=middle+1;
            else
                return middle;
        }
        return -1;
    }
}</arr>
登入後複製

以上是Java的二分查找實作原理及程式碼實現的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:yisu.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板