二分查找法

二分查找法：（来源百度百科）首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

Java实现二分查找，代码如下：

/**
 * 二分查找法
 *
 * @author zlm
 */
public class DichotomyFind {

    public static void main(String[] args) {
        // 获取数组
        int[] array = randomArray();
        // 排序
        sort(array);
        // 获取要查找的数字
        int num = toop(array);
        // 查找下标
        int index = dichotomy(array, num);
        // 打印
        print(num, index);
    }

    private static int toop(int[] array) {
        System.out.print("您要查找的数组是：");
        System.out.println(Arrays.toString(array));
        System.out.println("=========================");
        System.out.print("请输入你要查找的数字：");
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        scanner.close();
        return num;
    }

    private static void print(int num, int index) {
        if (index == -1) {
            System.out.println("抱歉，您要查找的数字在数组中不存在");
        } else {
            System.out.println("您要查找的数字" + num + "的下标是" + index);
        }
    }

    /**
     * 二分查找
     *
     * @param array 要查找的数组
     * @param num   要查找的数字
     * @return 数字下标
     */
    private static int dichotomy(int[] array, int num) {
        int startIndex = 0;
        int endIndex = array.length - 1;
        while (startIndex <= endIndex) {
            int minIndex = (startIndex + endIndex) / 2;
            if (num < array[minIndex]) {
                // 在前半段
                endIndex = minIndex - 1;
            } else if (num > array[minIndex]) {
                // 在后半段
                startIndex = minIndex + 1;
            } else if (num == array[minIndex]) {
                // 找着了
                return minIndex;
            }
        }

        return -1;
    }

    /**
     * 获取随机10长度的数组
     *
     * @return 随机数组
     */
    private static int[] randomArray() {
        int[] array = new int[10];
        for (int i = 0; i < array.length; i++) {
            array[i] = (int) Math.floor(Math.random() * 100);
        }
        return array;
    }

    /**
     * 冒泡排序
     *
     * @param array 排序数组
     */
    private static void sort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int j = 0; j < array.length - i; j++) {
                if (array[j] > array[j + 1]) {
                    int t = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = t;
                }
            }
        }
    }
}