算法数据与结构——简单的线性查找法超级大汇总—

LinearSearch

public class LinearSearch {
    private LinearSearch() {
    }

    public static <A> int search(A[] data, A target) {
        for (int i = 0; i < data.length; i++)
            if (data[i].equals(target))
                return i;

        return -1;
    }

    public static void main(String[] args) {
        Integer[] data = {24, 18, 12, 9, 16, 66, 32, 4};
        int res = LinearSearch.search(data, 16);
        System.out.println(res);


        int res2 = LinearSearch.search(data, 126);
        System.out.println(res2);
    }

}

温馨提示

这里我们要注意的地方有两个，一个就是判断数组中的内容的时候最好是使用.equals，不然可能会出现其他错误，至于==和.equals有什么区别可以看其他的文章。
第二个要注意的地方就是，在我们定义数组的时候，必须要使用包装类，上面的例子就是Integer，不然编译器会报错。
上面的泛型我用的是A，似乎规范一些应该用E，我这里的意思是泛型用什么对结果不会有影响！

让我们来看看一个自定义类的操作

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

    public static void main(String[] args) {
//        Integer[] data = {24, 18, 12, 9, 16, 66, 32, 4};
//        int res = LinearSearch.search(data, 16);
//        System.out.println(res);
//
//
//        int res2 = LinearSearch.search(data, 126);
//        System.out.println(res2);

        Student[] students = {new Student("aaa"), new Student("ddd"),new Student("www")};
        Student aaa = new Student("aaA");
        int res3 = LinearSearch.search(students,aaa);
        System.out.println(res3);
    }

}

public class Student {
    private String name;

    public Student(String name) {
        this.name = name;
    }

    @Override
    public boolean equals(Object student){
        if (this==student)
            return true;
        if (student==null)
            return false;
        if (this.getClass() != student.getClass())
            return false;
        Student another = (Student) student;
        return this.name.toLowerCase().equals(another.name.toLowerCase());
    }

}

温馨提示

这里有两个需要注意的点，我们可以发现，我们之前的equals是对比的字符串，而如果我们代码不变的话，程序会一直运行找不到的输出，这是因为我们是一个对象，这个时候我们就需要重写一下student的equals方法了，细心的也会发现，我还加了这个.toLowerCase()，这个是不区分大小写的意思，这样我们就可以成功拿到我们想要的了

需要注意的点

这里我们需要注意，虽然我们重写了student，但是也是需要创建一个对象的喔。千万不要直接对比字符串，要不然也是得不到我们想要的

这里是一种设计思想，在后面可能就不会说得那么细了，未来这种思想会贯穿整个算法结构，后面的算法会越来越复杂，期待吧！

复杂度分析：表示算法的性能

咱们之前的小例子

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

如何分析复杂度

1.通常看最差的情况
2.算法运行的上界（最差也就这样了）
3.O(n) 常数不重要复杂度描述的是随着数据规模n的增大，算法性能的变化趋势
我们看下面这个小例子：T1 = 10000n T2=2n^2 O(n) < O(n^2) 这是为什么呢？我们相信一定存在某个临界点n0，当n >= n0,T1 < T2 数学小例子：10000n < 2n^2 解得：n > 5000 n0 > 5000
可得：当n > 5000的时候，第一个算法将反超第二个算法，当n更加大的时候，第一个算法将大大的超越，几百万的N的时候，第一个算法的速度将碾压第二个算法！

我们先看一张图

温馨提示

在每一个循环开始的时候data[0...i-1]中没有找到目标——这就是循环不变量

循环体：维持循环不变量

目前我们的循环体比较简单，在后期我们复杂的算法逻辑的时候，我们才会更加清晰的了解循环不变量的意义，这里先有一个小理解！

写出正确的代码：1.定义清楚循环不变量 2.维护循环不变量 3.定义清楚函数的功能

温馨提示

咱们之前的小例子：LinearSearch
输入：数组，和目标元素
输出：目标元素所在的索引；若不存在，返回-1

常见的算法复杂度

空间复杂度

温馨提示

在现在的时代里面，我们一般不在意空间复杂度，而更加的在意时间复杂度，因为现在的计算机内存越来越大，而控件也就越来越大，所以我们更希望的是使用空间换时间！

测试时间复杂度

ArrayGenerator

public class ArrayGenerator {
    private ArrayGenerator() {
    }


    public static Integer[] generateOrderedArray(int n) {
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++)
            arr[i] = i;
            return arr;

    }
}

    public static void main(String[] args) {

        int [] dataSize = {1000000,10000000};
        for(int n :dataSize){
            Integer[] data = ArrayGenerator.generateOrderedArray(n);

            long startTime = System.nanoTime();
            for (int k = 0;k<100;k++)
                LinearSearch.search(data, n);
            long endTime = System.nanoTime();
            double time = (endTime - startTime) / 1000000000.0;
            System.out.println("n = "+n+",100 runs :"+time + "s");
        }

控制台输出

温馨提示

这里我们可以简单的看到100万数据，和1000万数据之间的区别，也开始了有对时间复杂度的相应理解。

本文作者为DBC，转载请注明。