算法-线性查找
线性查找是一种最简单的查找方法，它的基本思想是从第一个记录开始，逐个比较记录的关键字，直到和给定的K值相等，则查找成功；若比较结果与文件中n个记录的关键字都不等，则查找失败。
查找是对具有相同属性的数据元素（记录）的集合（数据对象）进行的，称之为表或文件，也称字典。对于表的查找，若仅对表进行查找操作，而不能改变表中的数据元素，为静态查找；对表除了进行查找操作外，还可能对表进行插入或删除操作，则为动态查找。
--百度百科
下面是相关代码的演进过程，先看第一版：
package com.wangjianlong.algorithm.linearSearch;
public class LinearSearch {
public int search(int[] data, int target) {
for (int i = 0; i < data.length; i++) {
if (data[i] == target) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr={1,2,3,4,5,1};
LinearSearch linearSearch=new LinearSearch();
int search = linearSearch.search(arr, 4);
System.out.println("search result:"+search);
}
}
我们对方法静态化，看看带来的使用改变：
package com.wangjianlong.algorithm.linearSearch;
public class LinearSearch {
//public int search(int[] data, int target) {
//这里将search方法用static修饰，作为静态方法
public static int search(int[] data, int target) {
for (int i = 0; i < data.length; i++) {
if (data[i] == target) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr={1,2,3,4,5,1};
//search已经是静态方法，不需要new LinearSearch对象，可以直接调用了
int search = LinearSearch.search(arr, 10);
System.out.println("search result:"+search);
}
}上面我们虽然对search方法进行了static修饰，但外部使用者依然可以继续new LinearSearch的，为了实现外部使用者只能通过静态调用 使用我们的算法库，还需要进行如下调整，我们将LinearSearch的构造方法声明为private：
package com.wangjianlong.algorithm.linearSearch;
public class LinearSearch {
//调整三：将构造方法设置为private，阻止外部使用者对LinearSearch的new操作
private LinearSearch(){}
//public int search(int[] data, int target) {
//这里将search方法用static修饰，作为静态方法
public static int search(int[] data, int target) {
for (int i = 0; i < data.length; i++) {
if (data[i] == target) {
return i;
}
}
return -1;
}
}经过上的改造，如果外部还想new我们的LinerSearch，就会被阻止了，效果见下图：
我们再仔细观察上述代码，就不难发现其中的缺陷，比如我们现在实现的这个入参是确定的，只能针对int类型数组进行查找，那我如果我们要查找字符串呢，浮点呢？为了解决这个问题，我们继续迭代改进。
package com.wangjianlong.algorithm.linearSearch;
public class LinearSearch {
private LinearSearch() {
}
//我们将方法增加一个泛型E
public static <E> int search(E[] data, E target) {
for (int i = 0; i < data.length; i++) {
if (data[i] == target) {
return i;
}
}
return -1;
}
}但上述改造后，我们的main方法调用里会报错
我们看到Idea给的编码提示是，让我把int[]修改为 Integer[]，这是因为java的泛型类型参数只能类类型，不能是基本类型的，我们调整下main里的代码，替换为基本类型对应的包装类：
package com.wangjianlong.algorithm.linearSearch;
public class Main {
public static void main(String[] args) {
// LinearSearch linearSearch=new LinearSearch();
//从int[] 修改为Integer[]，以适配search方法的泛型参数要求
Integer[] arr={1,2,3,4,5,1};
//search已经是静态方法，不需要new LinearSearch对象，可以直接调用了
int search = LinearSearch.search(arr, 10);
System.out.println("search result:"+search);
}
}我们还有一个细节需要处理，我们现在修改为支持泛型了，判等的地方需要调整
package com.wangjianlong.algorithm.linearSearch;
public class LinearSearch {
private LinearSearch() {
}
//我们将方法增加一个泛型E
public static <E> int search(E[] data, E target) {
for (int i = 0; i < data.length; i++) {
//这里也需要修改，不能用==判断了，因为==判断的是引用相等，我们想判断是值相等
//这里要从==修改为equals
if (data[i].equals(target)) {
return i;
}
}
return -1;
}
}在Java中 “==”用来判断基本数据类型的值是否相等，“equals”用来比较引用数据类型的时候，默认比较的是两个对象的引用地址是否一致，如果我们想实现比较对象的具体内容是否相同的时候，是需要在类里重写equals方法的，如下代码片段
package com.wangjianlong.algorithm.linearSearch;
public class Student {
private String name;
public Student(String name) {
this.name = name;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (this.getClass() != obj.getClass()) {
return false;
}
Student another = (Student) obj;
//这里的equals调用的String类的equals了，比较的是字符串值是否一样
return this.name.equals(another.name);
}
}
功能实现了，一般算法设计好了，我们需要进行一些测试工作。来验证我们算法的效率。本练习中，我们设计一个数字生产类，用于生产出用于测试的数组：
package com.wangjianlong.algorithm.linearSearch;
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;
}
}
我们在main函数中进行测试统计，为了减少干扰，我们可以对算法进行多次调用，这里我们调用100次，然后得到一个耗时情况：
package com.wangjianlong.algorithm.linearSearch;
public class Main {
public static void main(String[] args) {
//设置不同的数据规模
int[] dataSize={1000000,10000000};
for (int n:dataSize){
Integer[] arr=ArrayGenerator.generateOrderedArray(n);
long start=System.nanoTime();
for (int k=0;k<100;k++){
LinearSearch.search(arr, n);
}
long end=System.nanoTime();
double time=(end-start)/1000000000.0;
System.out.println("n="+n+ ", 100 runs used:"+time+" s");
}
}
}这样我们就更直观科学的得到测试的结论，我电脑上的输出结果是这样的：
n=1000000, 100 runs used:0.1733074 s
n=10000000, 100 runs used:1.4217724 s以上是本次学习的全部内容，关于算法的学习，后面继续学习和整理。
- 点赞
- 收藏
- 关注作者
评论（0）