二分查找

二分查找

• 二分查找就是返回有序序列中，需要查找的元素索引，无则-1。

    需求：二分查找：手写实现数组元素的查找，存在返回索引，无则返回 -1；

        实现思路：（前提是有序的序列）
                1、 如果不是有序的数组，我们先排序（选择、冒泡）任意；
                2、 创建三个指针，分别为：第一个元素指针和最后一个指针以及中间元素的指针
                3、 确保条件成立（min < max），方可继续执行查找，否则没有
                4、 判断是否相等，相等返回索引，否则返回 -

4.1 代码示例 （这里采用乱序数组）

public class DichotomyFind {
    public static void main(String[] LiuJinTao) {
        
        // 创建一个数组，很明显，这我故意设置为乱序的，目的是为了复习排序
        int [] arr = {11, 33, 55, 22, 44, 99, 77, 66, 88, 100};
        // 这里为了清晰明了，这里我使用方法来进行封装
        /**
         *  数组排序
         */
        SelectSortHandle(arr);
        /**
         *  二分查找
         */
        int result = DichotomyFindHandle(arr, 100);
        System.out.println(result);
        

    }
    
    
    /**
     * 二分查找
     * @param arr
     * @param element
     * @return
     */
    private static int DichotomyFindHandle(int [] arr, int element) {
        // 2. 创建指针
        int min = 0;
        int max = arr.length - 1;
        int mid;
        // 3. 根据条件是否成立，决定是否查找
        while (min <= max) {
            mid = (min + max) / 2;
            // 4. 判断是否相等，注意的是记得调整min和max的指针位置
            if (element < arr[mid]) {
                max = mid - 1;
            } else if (element > arr[mid]) {
                min = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
    
    
    /**
     * 选择排序数组
     * @param arr
     */
    private static void SelectSortHandle(int[] arr) {
        // 1. 二分查找前提处理
        for (int i = 0; i < arr.length - 1; i++) {
            // 这里选择排序
            for (int j = i + 1; j < arr.length; j++) {
                // 下标为 0 开始，向后面元素进行判断比较。
                if (arr[i] > arr[j]) {
                    // 当前面的元素大于后面的元素，就交换位置，然后从下标 1 开始，以此类推
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        // 查看排序结果 → 将 int 数组 格式化为 String类型输出
        System.out.println(Arrays.toString(arr)); //[11, 22, 33, 44, 55, 66, 77, 88, 99]
    }
}