網(wǎng)上找到的圖片便于理解

二分查找遞歸實(shí)現(xiàn)與循環(huán)實(shí)現(xiàn)代碼：

image.png

/**

• 二分查找
• 1.二分查找又稱折半查找进宝，它是一種效率較高的查找方法。
• 2.二分查找要求：（1）必須采用順序存儲結(jié)構(gòu) （2）.必須按關(guān)鍵字大小有序排列
• 3.原理：將數(shù)組分為三部分，依次是中值（所謂的中值就是數(shù)組中間位置的那個(gè)值）前珊膜，中值吗跋，中值后
• 將要查找的值和數(shù)組的中值進(jìn)行比較，若小于中值則在中值前 面找哨颂，若大于中值則在中值后面找喷市，
• 等于中值時(shí)直接返回。然后依次是一個(gè)遞歸過程威恼，將前半部分或者后半部分繼續(xù)分解為三部分品姓。
• 4.實(shí)現(xiàn)：
• 二分查找的實(shí)現(xiàn)用遞歸和循環(huán)兩種方式
  */

public class _00BinarySearch {
    public static void main(String[] args) {
        int[] arr = {6, 12, 33, 87, 90, 97, 108, 561};
        System.out.println("循環(huán)查找:" + binarySearch(arr, 87));
        System.out.println("遞歸查找:" + binSearch(arr, 0, arr.length - 1, 87));
    }

    //循環(huán)實(shí)現(xiàn)二分查找算法arr 已排好序的數(shù)組x 需要查找的數(shù)-1 無法查到數(shù)據(jù)
    public static int binarySearch(int[] srcArray, int des) {
        //定義初始最小、最大索引
        int low = 0;
        int high = srcArray.length - 1;
        //確保不會出現(xiàn)重復(fù)查找箫措，越界
        while (low <= high) {
            //計(jì)算出中間索引值
            int middle = (high + low) >>> 1;//防止溢出
            if (des == srcArray[middle]) {
                return middle;
                //判斷下限
            } else if (des < srcArray[middle]) {
                high = middle - 1;
                //判斷上限
            } else {
                low = middle + 1;
            }
        }
        //若沒有腹备，則返回-1
        return -1;
    }

    /**
     * 二分查找遞歸實(shí)現(xiàn)。
     * @param srcArray 有序數(shù)組
     * @param start    數(shù)組低地址下標(biāo)
     * @param end      數(shù)組高地址下標(biāo)
     * @param key      查找元素
     * @return 查找元素不存在返回-1
     */
    public static int binSearch(int srcArray[], int start, int end, int key) {
//        int mid = (end - start) / 2 + start;
        int mid = (end - start) >>> 1;
        if (srcArray[mid] == key) {
            return mid;
        }
        if (start >= end) {
            return -1;
        } else if (key > srcArray[mid]) {
            return binSearch(srcArray, mid + 1, end, key);
        } else if (key < srcArray[mid]) {
            return binSearch(srcArray, start, mid - 1, key);
        }
        return -1;
    }
}