查找算法总结

顺序查找

代码很简单，循环比较即可。

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

二分查找

前提：必须是有序的数据。

基本思想：把一个有序的数据一份为二。然后判断是比目标数据大了还是小了，如果小了往左边的部分找；如果大了往右边的数据找。确定了找的方向后再次把数据一分为二，继续上面的步骤直到找到为止。这里的重复执行就用递归思想。

    public static void binerySearch(int[] array, int start, int end, int num) {
        int middle = (start + end) / 2;
        if (array[middle] == num) {
            System.out.print("找到第" + middle + "个位置");
        } else if (array[middle] > num) {
            binerySearch(array, start, middle - 1, num);
        } else if (array[middle] < num) {
            binerySearch(array, middle + 1, end, num);
        }
    }

方法测试：

    public static void main(String[] args) {
        int[] array = new int[]{7, -3, 0, 20, 8, 9};

        int position = search(array, 20);
        if (position == -1) {
            System.out.println("没有找到该数");
        } else {
            System.out.println("找到第" + position + "个位置");
        }

        int[] array2 = new int[]{-2,5,10,16,87,99};
        binerySearch(array2,0,array2.length,10);
    }

插值查找

我们可以将查找的点改进为如下：
　　mid=low+(key-a[low])/(a[high]-a[low])*(high-low)。基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。

斐波那契查找

基本思想：也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。

分块查找

算法思想：将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素

哈希查找

Hash是一种典型以空间换时间的算法，比如原来一个长度为100的数组，对其查找，只需要遍历且匹配相应记录即可，从空间复杂度上来看，假如数组存储的是byte类型数据，那么该数组占用100byte空间。现在我们采用Hash算法，我们前面说的Hash必须有一个规则，约束键与存储位置的关系，那么就需要一个固定长度的hash表，此时，仍然是100byte的数组，假设我们需要的100byte用来记录键与位置的关系，那么总的空间为200byte，而且用于记录规则的表大小会根据规则，大小可能是不定的。单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)。