04、数据结构与算法 - 基础：查找算法

二分查找算法

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好，占用系统内存较少；其缺点是要求待查表为有序表，且插入删除困难。这个是基础，最简单的查找算法了。

 public static void main(String[] args) {
        int srcArray[] = {3, 5, 11, 17, 21, 23, 28, 30, 32, 50, 64, 78, 81, 95, 101};
        System.out.println(binSearch(srcArray, 95));
    }

    /**
     * 二分查找针对的是有序的数组
     * 二分查找普通循环实现
     *
     * @param srcArray 有序数组
     * @param key      查找元素
     * @return
     */
    public static int binSearch(int srcArray[], int key) {
        if (srcArray.length <= 0) {
            return -1;
        }
        // 取出首尾判断key是否在指定的srcArray中
        int first = srcArray[0];
        int end = srcArray[srcArray.length - 1];
        if (key < first || key > end) {
            return -1;
        }
        int mid = srcArray.length / 2;
        if (key == srcArray[mid]) {
            return mid;
        }
        //二分核心逻辑
        int startIndex = 0;
        int endIndex = srcArray.length - 1;
        while (startIndex <= endIndex) {
            mid = (endIndex - startIndex) / 2 + startIndex;
            if (key < srcArray[mid]) {
                endIndex = mid - 1;
            } else if (key > srcArray[mid]) {
                startIndex = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

二分查找算法如果没有用到递归方法的话，只会影响CPU。对内存模型来说影响不大。时间复杂度log2n，2的开方。空间复杂度是2。一定要牢记这个算法。应用的地方也是非常广泛，平衡树里面大量采用。

递归实现二分查找

递归简单理解就是方法自身调用自身。

 public static void main(String[] args) {
        int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
        System.out.println(binSearch(srcArray, 0,15,28));
    }
    /**
     * 二分查找递归实现
     *
     * @param srcArray  有序数组
     * @param start 数组低地址下标
     * @param end   数组高地址下标
     * @param key  查找元素
     * @return 查找元素不存在返回-1
     */
    public static int binSearch(int srcArray[], int start, int end, int key) {
        int mid = (end - start) / 2 + start;
        if (srcArray[mid] == key) {
            return mid;
        }
        if (start >= end) {
            return -1;
        } else if (key > srcArray[mid]) {
            return binSearch(srcArray, mid + 1, end, key);
        } else if (key < srcArray[mid]) {
            return binSearch(srcArray, start, mid - 1, key);
        }
        return -1;
    }

递归几乎会经常用到，需要注意的一点是：递归不光影响的CPU。JVM里面的线程栈空间也会变大。所以当递归的调用链长的时候需要-Xss设置线程栈的大小。