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

1.二分查找步驟描述

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

（2）用將關鍵字值與中間位置的關鍵字值比較；

若相等，則查找成功

#若大於，則在後（右）半個區域繼續進行折半查找

若小於，則在前（左）半個區域繼續進行折半查找

（3）對確定的縮小區域再按折半公式，重複上述步驟。

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

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中文網其他相關文章！