【Java】数据结构-线性查找法

什么是算法

• 一、有限性

• 二、确定性：不会产生二义性

• 三、可行性

• 四、输入

• 五、输出

线性查找法

使用泛型

• 不可以是基本数据类型，只能是类对象

  • 基本数据类型：boolean,byte,char,short,int,long,float,double

• 每个基本数据类型都有对应的包装类

  • Boolean, Byte, Character, Short, Integer, Long, Float, Double

线性查找法Java执行结果截图

线性查找法Java代码

LinearSearch.java

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)) //equals用于值相等，尽量不写==
                return i;

        return -1;
    }

    public static void main(String[] args){

        Integer[] data = {24, 18, 12, 9, 16, 66, 32, 4}; //手动修改数组类型


        int res1 = LinearSearch.search(data, 16);  //自动转换泛型类，数组型不能
        System.out.println(res1);

        int res2 = LinearSearch.search(data, 666);
        System.out.println(res2);
//以下代码可不需要-----------------------------
        Student[] students = {new Student("Alice"),
                              new Student("Bob"),
                              new Student("Charles")};
        Student bob = new Student("bOb"); //不区分大小写
        int res3 = LinearSearch.search(students, bob);
        System.out.println(res3);
    }
}

Student.java

import java.util.Locale;
//以下代码可不需要-----------------------------
public class Student {

    private String name;

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

    @Override
    public boolean equals(Object student){ //student是Object的对象
        if(this == student) //判断对象是否等于student
            return true;
        if(student == null)
            return false;
        if(this.getClass() != student.getClass()) //当前的类对象是否等于object这个student类对象
            return false;

        Student another = (Student)student; //将student转换为Student 进行覆盖
        return this.name.toLowerCase().equals(another.name.toLowerCase()); //toLowerCase转小写，进行不区分大小写
    }
}

线性查找算法运行结果截图

线性查找法算法时间测试

LinearSearch.java

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)) //equals用于值相等，尽量不写==
                return i;

        return -1;
    }

    public static void main(String[] args){

        int[] dataSize = {10000000,100000000};
        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 + ", 1000 runs :" + time + " s"); //打印出花费时间
        }
//        int res2 = LinearSearch.search(data, 666);
//        System.out.println(res2);

        Student[] students = {new Student("Alice"),
                              new Student("Bob"),
                              new Student("Charles")};
        Student bob = new Student("bOb"); //不区分大小写
        int res3 = LinearSearch.search(students, bob);
        System.out.println(res3);
    }
}