2、线性查找法

【数据结构与算法基础】代码仓库：https://github.com/jinrunheng/datastructure-and-algorithm

一：最简单的算法——线性查找法

首先，让我们正式来认识一下，什么是算法。

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的，清晰，可执行的计算机指令。算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。在上一章节，我们介绍了时间复杂度与空间复杂度这两个概念，时间复杂度和空间复杂度可以衡量一个具体的算法的优劣。

Knuth 在他的巨著 The Art of Computer Programming 中提出算法应具备五大特性：

1. 输入：一个算法必须有零个或以上输入量。
2. 输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。
3. 明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地符合要求或期望，通常要求实际运行结果是确定的。
4. 有限性：依据图灵的定义，一个算法是能够被任何图灵完备系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。
5. 有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

在理解了算法的基本概念后，我们来认识第一个也是最简单的算法——线性查找法。

线性查找法（Linear Search）也称作线性搜索或顺序搜索法，指按一定顺序检查数组中的每一个元素，直到找到所要寻找的特定值为止。线性查找法是最简单的一种搜索算法。

示例：

在一个数组 data 中，查找元素 target，若存在则返回目标元素的索引值，若不存在则返回 -1

代码如下：

int getTargetIndexOfData(int[] data,int target){
    for(int i = 0; i < data.length; i++)
        if(data[i] == target)
            return i;
    return -1;        
}

这就是线性查找法，接下来，我们将线性查找法封装成属于我们自己的方法类。

二：线性查找法的实现与封装

代码链接🔗

在上面的示例中，输入数组为 int 型，但是，我们需要考虑输入的数组可以为不同类型时的情况。

我们可以使用 Java 的泛型。

使用泛型后，我们的 LinearSearch 代码如下：

public class LinearSearch {
    private LinearSearch() {
    }
    public static <E> int search(E[] data, E target) {
        for (int i = 0; i < data.length; i++)
            if (data[i].equals(target))
                return i;
        return -1;
    }
}

三：循环不变量

线性查找法的本质就是循环遍历数组，让目标值与每次遍历的元素进行比对。我们可以通过这个基本的算法认识到，循环是算法中构建逻辑非常重要的方式之一。

接下来，我们来认识一个重要的概念：循环不变量。

什么是循环不变量呢？

循环不变量（loop invariant）是一组在循环体内，每次迭代均保持为真的性质的表达式。

拿线性查找这个算法来举例：

我们在每一轮遍历，都会确认当前的 data[i] 是否为我们查找的目标值，当遍历到 data[i] 时，我们可以确定的一个前提是，在 data[0… i - 1] 这个区间内没有找到目标，以后的循环中，我们也可以确定在这个范围没有我们要找的目标值。这就是循环不变量。而循环体本身的目的就是在维持循环不变量。

对于线性查找这个简单的算法来说，循环不变量这个概念似乎有一些鸡肋，不过随着后续我们讲解到非常复杂的算法时，搞清循环不变量是非常重要的。

四：线性查找法的复杂度分析与验证

对于线性查找法，时间复杂度为 O(N)，空间复杂度为 O(1)。接下来我们使用程序来测试一下算法的性能：

@Test
void performanceTest() {
    int[] dataSize = {100_0000, 1000_0000};
    for (int size : dataSize) {
        Integer[] testData = ArrayGenerator.generateOrderedArray(size); // 随机生成有序的数组
        long start = System.nanoTime();
        for (int i = 0; i < 10; i++)
                LinearSearch.search(testData, size);
        long end = System.nanoTime();
        System.out.println("t : " + (end - start) / 1000000000.0 + "s");
    }
}

对于一百万和一千万这两个量级的数据，程序的运行结果如下：

t : 0.0187213s
t : 0.1367794s

我们可以看到，当数据规模成 10 倍变化时，运行的速度也是近似为 10 倍的关系。这也间接地验证了线性查找这种算法的时间复杂度为 O(n)。