线性查找：面对线性数据结构进行的查找算法（链表，数组）
同时，为了实现泛型，需要对类的 equals 方法进行重写

一、原理：

1.对于数组：

就是利用下标对数组进行遍历，然后直到获得目标值。
输入：数组， 目标元素
输出：目标元素所在索引；若不存在，返回 -1

2.对于链表：

利用 Node 节点的 next 指向，对 node 进行遍历，进行查找。
输入：目标元素
输出：boolean ( 是否存在该值 )，或者使用 index 记录所在顺序。
若不存在，返回 -1；

  • 数组在内存中存储位置连续分布，而链表不行，所以链表无法使用 foreach 循环进行遍历

    二、简单实现：

    第一版

    1. public class LinerFind {
    2.   public int search(int[] data, int target){
    3.       for(int i = 0;i<data.length;i++){
    4.           if(data[i] == target){
    5.               return i;
    6.           }
    7.       }
    8.       return -1;
    9.   }
    10.   //单元测试
    11.   public static void main(String[] args) {
    12.       int[] data = {1,23,4,56,66,780,546};
    13.       LinerFind lf = new LinerFind();
    14.       int res = lf.search(data, 1);
    15.       System.out.println(res);
    16.   }
    17. }

// LinerFind 是一个动态词汇， 最好把 search 方法写成静态方法， 这样调用 就不需要创建对象

思考一下 Math 和 Integer.parseInt() 也没有创建对象后再进行使用，因为并不需要创建对象，只是想操作这个对象。
将 search 方法定义为 static 方法， 并将构造函数定义为 private ，这样用户就不会使用构造了。

第二版（应对不同的数据类型，避免重复）

复习一下泛型，泛型需要使用的为类对象，而不是基本数据类型，所以产生类对应的包装类。

  • 泛型类型 不能适用于静态方法，使用其他类型区分，将静态方法的泛型类型和实例类型的泛型类型区分开。
    1. // 使用泛型(java中的 map, list 等都是使用泛型类)
    2. private LinearSearch2(){}
    3.    public static <T> int search(T[] data, T target){
    4.         for(int i = 0;i<data.length;i++){
    5.              if(data[i].equals(target)){  // 此时为两个类对象，使用 equals 不用 ==
    6.                   return i;
    7.              }
    8.         }
    9.         return -1;
    10.    }
    11.    public static void main(String[] args) {
    12.         Integer[] data = {1,23,4,56,66,780,546};
    13.         int res = LinearSearch2.search(data, 1);
    14.         System.out.println(res);
    15.    }

作业：自己写一个类。重写 equals()，避免产生错误:

  1. public class Student {
  2.     private int age;
  3.     private String name;
  5.     public Student(int age, String name) {
  6.         this.age = age;
  7.         this.name = name;
  8.     }
  10.     public int getAge(){
  11.         return this.age;
  12.     }
  14.     public String getName(){
  15.         return this.name;
  16.     }
  18.     // 判断对象是否为空或者为统一类型
  19.     // 然后再比较值判断相等
  20.     @Override
  21.     public boolean equals(Object obj) {
  22.         if (obj == null || !(obj instanceof Student)) {
  23.             return false;
  24.         }
  25.         Student o = (Student) obj;
  26.         return (this.age == o.getAge() && this.name.equals((o.getName()));
  27.     }
  28. }

三、循环不变量：

在循环过程中，始终不变的条件，为循环不变量。

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

通常看最差的情况：
n = data.length T = n O(n) 性能与数据规模 n 之间的关系
T1 = 1000n O(n) T2=2n^2 O(n^2)

1.常见复杂度(时间)):

  1. while(n){
  2.     n%2;
  3.     n/=2;
  4. }
  5. O(logn)

长度为 n 的二进制数字 O(2^n)
长度为n的数组的所有排列 O(n!)

2.空间复杂度