查找算法

线性查找

顺序查找

按照顺序遍历与所查找的数进行比较

public static int search(int[] arry, int des) {
        for (int i = 0; i <= arry.length - 1; i++) {
            if (des == arry[i])
                return i;
        }
        return -1;
}

查找的时间复杂度为N，插入的时间复杂度为N

二分查找

二分查找要求元素必须是有顺序的，每次中间值与所要查找的数进行比较，如果要找的元素值小于中间值，则将待查序列缩小为左半部分，否则为右半部分，通过一次比较，将查找区间缩小一半

public static int search(int[] arr,int des){
    int start = 0;
    int end = arr.length - 1;
    // start > end 即表示没有找到
    while (start <= end){
        // 中间索引
        int mid = (start + end )/2;
        if(arr[mid] == des){
            return mid;
        } else if(arr[mid] > des){
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }

    return -1;
}

查找的时间复杂度为 $log{2}n$，插入的时间复杂度为 $log{2}n$

分块查找

分块查找是顺序查找和二分查找的整合，把一个大的线性表分为若干块，每块中找到一个最大值以及起始索引组成索引表，要求索引表是有序的，块与块之间需要排序，而对于每块内的节点没有排序要求

查找树

二叉查找树

二叉查找树的特点

每个节点只能有一个父节点指向自己(除根节点外，根节点没有父节点)
若它的左子树不空，则其左子树中所有节点的值不大于根节点的值
若它的右子树不空，则其右子树中所有节点的值不小于根节点的值
它的左右子树都是二叉查找树

使用二叉查找树来进行查找的方法是从根节点开始，递归的缩小查找范围，待查关键字与根节点元素关键字比较，若相等则返回根节点；若待查关键字小，则递归的在查找树的左子树中查找，否则递归在查找树的右子树中查找

public static class BST<K extends Comparable, V> {

        private Node root;

        private class Node {
            private K key;
            private V value;
            private Node left, right;
            private int N; // 以该节点为根的树中的节点总数

            public Node(K key, V value, int n) {
                this.key = key;
                this.value = value;
                N = n;
            }
        }

        public int size() {
            return size(root);
        }

        private int size(Node node) {
            if (node == null)
                return 0;
            else
                return node.N;
        }

        public V get(K key) {
            if(key == null)
                throw new RuntimeException("不允许为空");
            return get(root, key);
        }

        /**
         * 以node为根节点的子树中查找key
         *
         * @param node
         * @param key
         * @return
         */
        private V get(Node node, K key) {
            if (node == null)
                throw new RuntimeException("不允许为空");
            // 比较大小
            int cmp = key.compareTo(node.key);
            if (cmp < 0)
                return get(node.left, key);
            else if (cmp > 0)
                return get(node.right, key);
            else return node.value;
        }

        public void put(K key, V value) {
            if(key == null)
                throw new RuntimeException("不允许为空");
            root = put(root, key, value);
        }

        private Node put(Node node, K key, V value) {
            // 树为空，则实例化该树
            if (node == null)
                return new Node(key, value, 1);
            // 比较大小
            int cmp = key.compareTo(node.key);
            // 小于父节点
            if (cmp < 0)
                // 放入左子树
                node.left = put(node.left, key, value);
            // 大于父节点
            else if (cmp > 0)
                // 放入右子树
                node.right = put(node.right, key, value);
            else
                node.value = value;
            // 节点数量 = 左子树数量 + 右子树数量 + 本身
            node.N = size(node.left) + size(node.right) + 1;
            return node;
        }
    }