线性查找
从一个数组里面找出指定的元素的位置。
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;
}
