二分查找详解

思路分析

1. 二分查找是经常使用的一种查找算法，查找速度快，只需要O（log n）时间复杂度
2. 但是二分查找要求原始数组是有序的，即要么升序，要么降序
3. 使用递归的思路，考虑递归结束的条件，即要么找到该元素，要么查找完数组还没有找到该元素，都结束递归
4. 源码及详解见下

源码及分析

/**
     * 二分查找，需要保证数组元素有序
     *
     * @param arr     要查找的原数组
     * @param left    左侧索引
     * @param right   右侧索引
     * @param findVal 要查找的值
     * @return 如果找到返回该值对应的索引，如果没有找到，返回 -1
     */
    public static int binarySearch(int[] arr, int left, int right, int findVal) {
        //如果数组查找完还没有找到，直接返回 -1
        if (left > right) {
            return -1;
        }
        //定义变量保存中间值和中间索引
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        //如果要查找的值在中间值的右边，则向右递归
        if (findVal > midVal) {
            return binarySearch(arr, mid + 1, right, findVal);
            //如果要查找的值在中间值的左边，则向左递归
        } else if (findVal < midVal) {
            return binarySearch(arr, left, mid - 1, findVal);
        } else {
            //否则找到要查找的值，直接返回
            return mid;
        }
    }