求职必会算法手把手教你二分法查找

当数组或者集合中存放的元素数量非常多的时候，想要跟踪具体某个元素的位置或者是否存在，常规方式是循环每一个元素直到找到要查找的元素为止。这样的查找方式效率非常低下，这个时候需要使用二分法来实现，提高查找效率。

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

百度百科是这样介绍二分法查找的：

假设数组是按升序排序的，对于给定的目标值aim，从数组的中间位置开始查找：1.若查找数据与中间元素值正好相等，则返回中间元素值的索引;2.若查找数值比中间值小，则以整个查找范围的前半部分作为新的查找范围;3.若查找数值比中间值大，则以整个查找范围的后半部分作为新的查找范围;注：查找成功返回索引，失败返回-1

public class BinarySearch { 
    public static void main(String[] args) { 
        // 生成一个随机数组 
        int[] array = suiji(); 
        // 对随机数组排序 
        Arrays.sort(array); 
        System.out.println("产生的随机数组为： " + Arrays.toString(array)); 
 
        System.out.println("要进行查找的值： "); 
        Scanner input = new Scanner(System.in); 
        // 进行查找的目标值 
        int aim = input.nextInt(); 
 
        // 使用二分法查找 
        int index = binarySearch(array, aim); 
        System.out.println("查找的值的索引位置： " + index); 
 
    } 
 
    /** 
     * 生成一个随机数组 
     *  
     * @return 返回值，返回一个随机数组 
     */ 
    private static int[] suiji() { 
        // random.nextInt(n)+m  返回m到m+n-1之间的随机数 
        int n = new Random().nextInt(6) + 5; 
        int[] array = new int[n]; 
        // 循环遍历为数组赋值 
        for (int i = 0; i < array.length;="" i++)="" {="" array[i]="new" random().nextint(100);="" }="" return="" array;="" }="" *="" *="" 二分法查找="" ---循环的方式实现="" *="" *="" @param="" array="" 要查找的数组="" *="" @param="" aim="" 要查找的值="" *="" @return="" 返回值，成功返回索引，失败返回-1="" */="" private="" static="" int="" binarysearch(int[]="" array,="" int="" aim)="" {="" 数组最小索引值="" int="" left="0;" 数组最大索引值="" int="" right="array.length" -="" 1;="" int="" mid;="" while="" (left=""><= right)="" {="" mid="(left" +="" right)="" 2;="" 若查找数值比中间值小，则以整个查找范围的前半部分作为新的查找范围="" if="" (aim="">< array[mid])="" {="" right="mid" -="" 1;="" 若查找数值比中间值大，则以整个查找范围的后半部分作为新的查找范围="" }="" else="" if="" (aim=""> array[mid]) { 
                left = mid + 1; 
                // 若查找数据与中间元素值正好相等，则放回中间元素值的索引 
            } else { 
                return mid; 
            } 
        } 
        return -1; 
    } 
} 

代码执行结果：

产生的随机数组为： [16, 33, 40, 46, 57, 63, 65, 71, 85] 
要进行查找的值：  
46 
查找的值的索引位置： 3 

若输入的值找不到，则返回-1

产生的随机数组为： [28, 41, 47, 56, 70, 81, 85, 88, 95] 
要进行查找的值：  
66 
查找的值的索引位置： -1 

public class BinarySearch2 { 
    public static void main(String[] args) { 
        // 生成一个随机数组 
        int[] array = suiji(); 
        // 对随机数组排序 
        Arrays.sort(array); 
        System.out.println("产生的随机数组为： " + Arrays.toString(array)); 
 
        System.out.println("要进行查找的值： "); 
        Scanner input = new Scanner(System.in); 
        // 进行查找的目标值 
        int aim = input.nextInt(); 
 
        // 使用二分法查找 
        int index = binarySearch(array, aim, 0, array.length - 1); 
        System.out.println("查找的值的索引位置： " + index); 
    } 
 
    /** 
     * 生成一个随机数组 
     * 
     * @return 返回值，返回一个随机数组 
     */ 
    private static int[] suiji() { 
        // Random.nextInt(n)+m  返回m到m+n-1之间的随机数 
        int n = new Random().nextInt(6) + 5; 
        int[] array = new int[n]; 
        // 循环遍历为数组赋值 
        for (int i = 0; i < array.length;="" i++)="" {="" array[i]="new" random().nextint(100);="" }="" return="" array;="" }="" *="" *="" 二分法查找="" ---递归的方式="" *="" *="" @param="" array="" 要查找的数组="" *="" @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) { 
            //如果中间值大于要找的值则从左边一半继续递归 
            return binarySearch(array, aim, left, mid - 1); 
        } else { 
            //如果中间值小于要找的值则从右边一半继续递归 
            return binarySearch(array, aim, mid + 1, array.length-1); 
        } 
    } 
} 

递归相较于循环，代码比较简洁，但是时间和空间消耗比较大，效率低。在实际的学习与工作中，根据情况选择使用。