简单算法：线性查找法

程序员文章站 2024-03-16 09:36:40

...

线性查找法：从数组起始位置依次比较判断是否包含需要的目标对象，若找到直接返回下标。

核心算法：

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

从设计层面来讲，所在类（假设当前类为LinearSearch）的构造方法应为私有的，禁止用户new一个LinearSearch对象。

private LinearSearch() {
    }

若需要在一个数组中查找某数对应的下标，则在主方法中声明该数组时应为基本数据类型对应的包装类型。

Integer[] data = {24, 18, 12, 9, 16, 66, 32, 4};
int res = LinearSearch.search(data, 16);
System.out.println(res);//4

若需要在一个对象（假设该对象为Student）数组中查找某对象对应的下标，则需要重写父类的equals方法。

@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.equals(another.name);//比较当前对象与目标对象的属性值是否相等
    }

性能测试：设计数组能够生成无限的数，通过时间戳来进行性能测试比较百万级与千万级的差距。

public class ArrayGennerator {
    private ArrayGennerator() {
    }

    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 = ArrayGennerator.generateOrderedArray(n);
            long startTime = System.nanoTime();
            LinearSearch.search(data, n);
            long endTime = System.nanoTime();
            double time = (endTime - startTime) / 1000000000.0;
            System.out.println("n =" + n +" , "+ time + "s");
        }
}