数据结构与算法——查找算法

数据的查找算法较排序算法简单，并且常用的查找方案只有几种。

• 顺序查找
• 二分查找
• 插值查找
• 斐波那契查找
• 树表查找
• 分块查找
• 哈希查找

查找算法的分类

根据具体的实现逻辑不同，大体上可以把查找算法分为两大类：静态查找、动态查找，

• 静态查找：指查找表中无删除和插入操作。
• 动态查找：指查找表中有删除和插入操作。

根据查找的前提条件可以分为两大类：无序查找、有序查找

• 无序查找：指序列元素可以乱序
• 有序查找：指序列元素需要按一定的顺序排列（从小到大或从大到小）

顺序查找

通过遍历序列，与每一个序列中的元素对比，如果一致则返回

• 顺序查找属于无序查找，但仍可应用于有序序列中
• 如果序列中的元素存在重复项，在无序序列中，则需要遍历完成全部的元素后，方可返回
• 如果序列中的元素存在重复项，在有序序列中，则先遍历值大于查找值后即可返回数据。

public int sequenceSearch(int value)
{
    for (int i = 0; i < this.data.length; i++) {
        if (value == this.data[i]) {
            return i;
        }
    }

    return -1;
}

二分查找

也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

• 二分查找属于有序查找
• 如果序列中的元素存在重复项，则在找到值后，需要在该值左右两边分别查找，直到找出所有数据方可返回
• 二分查找的时间复杂度为log2n，所以如果存在1000个数，则最多需要10次才能找到数据

public int binarySearch(int value)
{
    return this.binarySearch(value, 0, this.data.length - 1);
}

protected int binarySearch(int value, int left, int right)
{
    if (left > right) {
        return -1;
    }
    int middle = (left + right) / 2;
    if (value == this.data[middle]) {
        return middle;
    } else if (this.data[middle] < value) {
        return binarySearch(value, middle + 1, right);
    } else {
        return binarySearch(value, left, middle - 1);
    }
}

差值查找

差值查找是通过预估查找值到左侧/右侧节点的位置设计出的一种算法

设一个有序序列data的元素个数为n，左节点为left，右节点为right。计算每个节点元素的平均增量值为insert_value = (right-left)/(data[right]-data[left])。预估计算查找值value到左侧节点值所需的节点长度insert_length = (value-left)insert_value; 这样，就可以预估出查找值所在的位置：middle=left+insert_length。 公式汇总：left + (value-left)(right-left)/(data[right]-data[left])。

• 差值查找属于有序查找
• 如果序列中的元素存在重复项，则在找到值后，需要在该值左右两边分别查找，直到找出所有数据方可返回
• 如果序列的分布不均匀，则所需时间不一定比二分查找要好，所以常用在均匀分布的有序序列中。

public int insertValueSearch(int value)
{
    return this.insertValueSearch(value, 0, this.data.length - 1);
}

protected int insertValueSearch(int value, int left, int right)
{
    if (left > right) {
        return -1;
    }
    int middle = left + ((value - this.data[left]) * (right - left) / (this.data[right] - this.data[left]));

    if (value == this.data[middle]) {
        return middle;
    } else if (this.data[middle] < value) {
        return insertValueSearch(value, middle + 1, right);
    } else {
        return insertValueSearch(value, left, middle - 1);
    }
}