1、二分法查找的背景

當(dāng)數(shù)組或者集合中存放的元素?cái)?shù)量非常多的時(shí)候，想要跟蹤具體某個(gè)元素的位置或者是否存在，常規(guī)方式是循環(huán)每一個(gè)元素直到找到要查找的元素為止。這樣的查找方式效率非常低下，這個(gè)時(shí)候需要使用二分法來實(shí)現(xiàn)，提高查找效率。

2、二分法查找的介紹

二分法查找(折半查找)，找指定數(shù)值所在的位置

百度百科是這樣介紹二分法查找的：

3、二分法查找的算法思想

假設(shè)數(shù)組是按升序排序的，對(duì)于給定的目標(biāo)值aim，從數(shù)組的中間位置開始查找：1.若查找數(shù)據(jù)與中間元素值正好相等，則返回中間元素值的索引;2.若查找數(shù)值比中間值小，則以整個(gè)查找范圍的前半部分作為新的查找范圍;3.若查找數(shù)值比中間值大，則以整個(gè)查找范圍的后半部分作為新的查找范圍;注：查找成功返回索引，失敗返回-1

4、代碼實(shí)現(xiàn)

4.1 利用循環(huán)的方式實(shí)現(xiàn)二分法查找

public class BinarySearch { 
    public static void main(String[] args) { 
        // 生成一個(gè)隨機(jī)數(shù)組 
        int[] array = suiji(); 
        // 對(duì)隨機(jī)數(shù)組排序 
        Arrays.sort(array); 
        System.out.println("產(chǎn)生的隨機(jī)數(shù)組為： " + Arrays.toString(array)); 
 
        System.out.println("要進(jìn)行查找的值： "); 
        Scanner input = new Scanner(System.in); 
        // 進(jìn)行查找的目標(biāo)值 
        int aim = input.nextInt(); 
 
        // 使用二分法查找 
        int index = binarySearch(array, aim); 
        System.out.println("查找的值的索引位置： " + index); 
 
    } 
 
    /** 
     * 生成一個(gè)隨機(jī)數(shù)組 
     *  
     * @return 返回值，返回一個(gè)隨機(jī)數(shù)組 
     */ 
    private static int[] suiji() { 
        // random.nextInt(n)+m  返回m到m+n-1之間的隨機(jī)數(shù) 
        int n = new Random().nextInt(6) + 5; 
        int[] array = new int[n]; 
        // 循環(huán)遍歷為數(shù)組賦值 
        for (int i = 0; i < array.length; i++) { 
            array[i] = new Random().nextInt(100); 
        } 
        return array; 
    } 
 
    /** 
     * 二分法查找  ---循環(huán)的方式實(shí)現(xiàn) 
     *  
     * @param array 要查找的數(shù)組 
     * @param aim 要查找的值 
     * @return 返回值，成功返回索引，失敗返回-1 
     */ 
    private static int binarySearch(int[] array, int aim) { 
        // 數(shù)組最小索引值 
        int left = 0; 
        // 數(shù)組最大索引值 
        int right = array.length - 1; 
        int mid; 
        while (left <= right) { 
            mid = (left + right) / 2; 
            // 若查找數(shù)值比中間值小，則以整個(gè)查找范圍的前半部分作為新的查找范圍 
            if (aim < array[mid]) { 
                right = mid - 1; 
                // 若查找數(shù)值比中間值大，則以整個(gè)查找范圍的后半部分作為新的查找范圍 
            } else if (aim > array[mid]) { 
                left = mid + 1; 
                // 若查找數(shù)據(jù)與中間元素值正好相等，則放回中間元素值的索引 
            } else { 
                return mid; 
            } 
        } 
        return -1; 
    } 
} 

代碼執(zhí)行結(jié)果：

產(chǎn)生的隨機(jī)數(shù)組為： [16, 33, 40, 46, 57, 63, 65, 71, 85] 
要進(jìn)行查找的值：  
46 
查找的值的索引位置： 3 

若輸入的值找不到，則返回-1

產(chǎn)生的隨機(jī)數(shù)組為： [28, 41, 47, 56, 70, 81, 85, 88, 95] 
要進(jìn)行查找的值：  
66 
查找的值的索引位置： -1 

4.2 利用遞歸的方式實(shí)現(xiàn)二分法查找

public class BinarySearch2 { 
    public static void main(String[] args) { 
        // 生成一個(gè)隨機(jī)數(shù)組 
        int[] array = suiji(); 
        // 對(duì)隨機(jī)數(shù)組排序 
        Arrays.sort(array); 
        System.out.println("產(chǎn)生的隨機(jī)數(shù)組為： " + Arrays.toString(array)); 
 
        System.out.println("要進(jìn)行查找的值： "); 
        Scanner input = new Scanner(System.in); 
        // 進(jìn)行查找的目標(biāo)值 
        int aim = input.nextInt(); 
 
        // 使用二分法查找 
        int index = binarySearch(array, aim, 0, array.length - 1); 
        System.out.println("查找的值的索引位置： " + index); 
    } 
 
    /** 
     * 生成一個(gè)隨機(jī)數(shù)組 
     * 
     * @return 返回值，返回一個(gè)隨機(jī)數(shù)組 
     */ 
    private static int[] suiji() { 
        // Random.nextInt(n)+m  返回m到m+n-1之間的隨機(jī)數(shù) 
        int n = new Random().nextInt(6) + 5; 
        int[] array = new int[n]; 
        // 循環(huán)遍歷為數(shù)組賦值 
        for (int i = 0; i < array.length; i++) { 
            array[i] = new Random().nextInt(100); 
        } 
        return array; 
    } 
 
    /** 
     * 二分法查找 ---遞歸的方式 
     * 
     * @param array 要查找的數(shù)組 
     * @param aim   要查找的值 
     * @param left  左邊最小值 
     * @param right 右邊最大值 
     * @return 返回值，成功返回索引，失敗返回-1 
     */ 
    private static int binarySearch(int[] array, int aim, int left, int right) { 
        if (aim < array[left] || aim > array[right]) { 
            return -1; 
        } 
        // 找中間值 
        int mid = (left + right) / 2; 
        if (array[mid] == aim) { 
            return mid; 
        } else if (array[mid] > aim) { 
            //如果中間值大于要找的值則從左邊一半繼續(xù)遞歸 
            return binarySearch(array, aim, left, mid - 1); 
        } else { 
            //如果中間值小于要找的值則從右邊一半繼續(xù)遞歸 
            return binarySearch(array, aim, mid + 1, array.length-1); 
        } 
    } 
} 

遞歸相較于循環(huán)，代碼比較簡(jiǎn)潔，但是時(shí)間和空間消耗比較大，效率低。在實(shí)際的學(xué)習(xí)與工作中，根據(jù)情況選擇使用。