基础的基础：线性查找

线性查找

从一个数组里面找出指定的元素的位置。

int实现

对于一个int数组的实现如下：

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

基于范型

对于Java语言来讲，基于范型可以适配各种类型

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;
}

循环不变量

找到循环不变量是实现算法的关键，一个算法很大程度就是在维护一个循环不变量。对于线性查找来说，其循环不变量为：
data[0...i)区间内的元素都不为target

算法复杂度

时间复杂度

算法复杂度是用来评价一个算法的性能，对于线性查找来讲其时间复杂度为O(n)

空间复杂度

对于现代计算机设备来讲，空间相对来讲不那么重要，通常会用空间来换时间。

算法测试

对于四个不同量级大小的数据，进行如下测试：

public static void main(String[] args) {
    int[] dataSize = {100000, 1000000, 10000000, 100000000};
    for (int len : dataSize) {
        Integer[] data = ArrayGenerator.generateOrderIntArray(len);
        long startTime = System.currentTimeMillis();
        LinearSearch.search(data, len - 1);
        long costTime = System.currentTimeMillis() - startTime;
        System.out.println(String.format("n = %d, costTime: %fS", len, costTime / 1000.0f));
    }
}

测试结果如下：

n = 100000, costTime: 0.005000S
n = 1000000, costTime: 0.014000S
n = 10000000, costTime: 2.284000S
n = 100000000, costTime: 28.025999S

可以看到，当数据量越大的时候，算法本身的性能对时间的影响就越精确，数据量从10000000增加到100000000，时间增加大概10倍，和算法复杂度O(n)一致。
对于数据的生成，由如下方法生成：

public static Integer[] generateOrderIntArray(int len) {
    Integer[] data = new Integer[len];
    for (int i = 0; i < len; i++) {
        data[i] = i;
    }
    return data;
}