七大查找算法

七大查找算法

七大查找算法 二分（折半）查找、插值查找、斐波那契查找、顺序查找、树表查找、分块查找、哈希查找。

1、二分查找

// 二分查找（递归）
public static int binarySearchRecursion(int[] ints, int key, int startIndex, int endIndex) {
    if (startIndex > endIndex) {
        return -1;
    }
    int midIndex = startIndex + (endIndex - startIndex) / 2;
    if (key == ints[midIndex]) {
        return midIndex;
    } else if (key < ints[midIndex]) {
        return binarySearchRecursion(ints, key, startIndex, midIndex - 1);
    } else {
        return binarySearchRecursion(ints, key, midIndex + 1, endIndex);
    }
}

// 二分查找（迭代）
public static int binarySearchIteration(int[] ints, int key, int startIndex, int endIndex) {
    while (startIndex <= endIndex) {
        int midIndex = (startIndex + endIndex) / 2;
        if (key == ints[midIndex]) {
            return midIndex;
        } else if (key < ints[midIndex]) {
            endIndex = midIndex - 1;
        } else {
            startIndex = midIndex + 1;
        }
    }
    return -1;
}

2、插值查找

// 插值查找（递归）
public static int insertionSearchRecursion(int[] ints, int key, int startIndex, int endIndex) {
    if (startIndex > endIndex) {
        return -1;
    } else if (startIndex == endIndex) {
        if (key == ints[startIndex]) {
            return startIndex;
        } else {
            return -1;
        }
    }

    int midIndex = startIndex + ((key - ints[startIndex]) / (ints[endIndex] - ints[startIndex])) * (endIndex - startIndex);

    if (midIndex > ints.length - 1 || midIndex < 0) {
        return -1;
    }

    if (key == ints[midIndex]) {
        return midIndex;
    } else if (key < ints[midIndex]) {
        return insertionSearchRecursion(ints, key, startIndex, midIndex - 1);
    } else {
        return insertionSearchRecursion(ints, key, midIndex + 1, endIndex);
    }
}

// 插值查找（迭代）
public static int insertionSearchIteration(int[] ints, int key, int startIndex, int endIndex) {
    while (startIndex <= endIndex) {

        int midIndex = startIndex + ((key - ints[startIndex]) / (ints[endIndex] - ints[startIndex])) * (endIndex - startIndex);

        if (midIndex > ints.length - 1 || midIndex < 0) {
            return -1;
        }

        if (key == ints[midIndex]) {
            return midIndex;
        } else if (key < ints[midIndex]) {
            endIndex = midIndex - 1;
        } else {
            startIndex = midIndex + 1;
        }
    }
    return -1;
}

3、斐波那契查找

// 斐波那契查找
public static int fibonacciSearch(int[] ints, int key) {
    int startIndex = 0, endIndex = ints.length - 1, k = 0;

    while (fib(k) - 1 < endIndex) {
        k++;
    }

    int[] temp;
    if (fib(k) == endIndex + 1) {
        temp = ints;
    } else {
        temp = Arrays.copyOf(ints, fib(k));
        for (int i = endIndex + 1; i < temp.length; i++) {
            temp[i] = ints[endIndex];
        }
    }

    while (startIndex <= endIndex) {
        int midIndex = startIndex + fib(k - 1) - 1;
        if (key == temp[midIndex]) {
            return midIndex;
        } else if (key < temp[midIndex]) {
            endIndex = midIndex - 1;
            k -= 1;
        } else {
            startIndex = midIndex + 1;
            k -= 2;
        }
    }
    return -1;
}

// 斐波那契数列（迭代）
public static int fib(int n) {
    if (n < 2) {
        return n;
    }
    int a = 0, b = 1, c = 0;
    for (int i = 2; i <= n; i++) {
        c = (a + b) % 1000000007;
        a = b;
        b = c;
    }
    return c;
}

4、顺序查找

// 顺序查找
public static int sequenceSearch1(int[] ints, int key) {
    for (int i = 0; i < ints.length; i++) {
        if (key == ints[i]) {
            return i;
        }
    }
    return -1;
}

5、树表查找

// 树表查找（二叉搜索树）
static class Node {
    private int index;
    private int value;
    private Node left;
    private Node right;
    public Node(int index, int value) {
        this.index = index;
        this.value = value;
    }
}

public static int treeSearch(int[] ints, int key) {
    Node root = new Node(0, ints[0]);
    for (int  i = 1; i < ints.length; i++) {
        buildTree(root, i, ints[i]);
    }

    return search(root, key);
}

public static int search(Node node, int key) {
    if (node == null) {
        return -1;
    }
    if (key == node.value) {
        return node.index;
    } else if (key < node.value) {
        return search(node.left, key);
    } else {
        return search(node.right, key);
    }
}

public static void buildTree(Node node, int index, int value) {
    if (value < node.value) {
        if (node.left == null) {
            node.left = new Node(index, value);
        } else {
            buildTree(node.left, index, value);
        }
    } else if (value > node.value) {
        if (node.right == null) {
            node.right = new Node(index, value);
        } else {
            buildTree(node.right, index, value);
        }
    }
}

6、分块查找

// 分块查找
static class Block {
    private int mark;
    private int startIndex;
    private int length;
    public Block(int mark, int startIndex, int length) {
        this.mark = mark;
        this.startIndex = startIndex;
        this.length = length;
    }
}

public static int blockSearch(int[] ints, int key) {
    Block[] blocks = new Block[] {
        new Block(ints[4], 0, 5),
        new Block(ints[9], 5, 5),
        new Block(ints[13], 10, 4)
    };

    Block block = null;
    for (Block block1 : blocks) {
        if (key > block1.mark) {
            continue;
        }
        block = block1;
        break;
    }

    if (block == null) {
        return -1;
    }

    return search(block, ints, key);
}

public static int search(Block block, int[] ints, int key) {
    for (int i = block.startIndex; i < block.startIndex + block.length; i++) {
        if (key == ints[i]) {
            return i;
        }
    }
    return -1;
}

7、哈希查找

// 哈希查找（见 java.util.HashMap）

@XGLLHZ - 张国荣 -《沉默是金》.mp3