📅前言
众所周知，算法与数据结构是所有计算机专业的同学必学的一门课程。算法不仅体现一个人的逻辑能力，更体现一个人的思维能力。它不单是学习算法与数据结构，更是深刻理解计算机科学。
那在本篇文章中，我们就来给算法做个开篇，并讲解最简单的一种算法，线性查找法。叮，开始讲解~
学完本篇文章，你将会收获到👇：
- 👏了解算法的基础知识
- 👏了解线性查找法的基本思想
- 👏使用
java语言实现一个简单的线性查找法
一、📝算法基础知识
1、什么是算法
算法是一些列解决问题的，清晰的，可执行的计算机指令。
生活中无处不充满着算法，比如说：在路上问路说怎么去天安门，那去天安门的各种路径，就是一种算法。
或者说，我们想问如何求解一元二次方程？这个求解的方法，也是一种算法。
还有可能是一道菜谱，比如说，如何做一道鱼香肉丝的菜。那它的各种做菜步骤，我们也可以把它视为是一种算法。
2、算法的五大特性
算法有五大特性，分别是：
- 有限性 —— 对于一个算法来说，它不应是无限循环的，而应该在有限的时间里去执行完。所谓有限的时间，不代表这个时间非常的短暂，只要是一个确定的时间，那么它就是有限的。
- 确定性 —— 所谓确定性，即不会产生二义性。比如说，我们现在要面对一片数据，这片数据描述的是一个班级中所有同学不同科目的考试成绩。那么我们在设计算法的时候，有可能其中一个指令是拿出成绩最高的一个学生的分数。但这时我们没有明确是哪个科目的最高成绩，在这个时候，程序就会产生二义性。因此，在设计算法时，我们应该明确其具体指令。
- 可行性 —— 算法中的每一步应该都是可行的。举个例子：假设现在有一个算法，这个算法明确的是拿出最大的质数。但其实，质数是有无穷个，不可能拿出最大的。所以，这个算法是不可行的。
- 输入 —— 对于一个算法来说，它肯定是有它需要操作的对象，那么它所操作的这些对象，就是算法的输入。
- 输出 —— 一个算法在执行完成后，总会有一个具体响应的结果，那么这个结果就是它的输出值。
二、📈线性查找法
1、举例阐述
线性查找法可以说是最简单的一种算法。那它是什么呢？举个例子🌰
假设现在有一沓卷子，我们要在这沓卷子中，找到属于自己的那张卷子。那么线性查找法的方法寻找的话，将按照下面的步骤：
- 第1张：不是
- 第2张：不是
- 第3张：不是
- ……
- 第5张：是！找到了！
如大家所看到的，线性查找法就是线性的，按照顺序一个个地去寻找。
2、实现线性查找法
假设现在有一组数组，我们要在数组中查找到某个具体数值的索引。那用线性查找法的方式，如何查找呢？首先我们新建一个 java 项目，并在项目的 src 文件夹下，新建一个 java 类，命名为 LinearSearch 。具体代码如下：
public class LinearSearch {
// data 是一个数组，target 是我们要查找的目标
// 括号里面是函数声明
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[] data = {
24, 45, 67, 12, 465, 78, 68};
LinearSearch ls = new LinearSearch();
int res = ls.search(data, 12);
System.out.println(res);
int res2 = ls.search(data, 888);
System.out.println(res2);
}
}
此时，控制台的输出为：
3
-1
大家可以看到，我们要找 12 这个数，它在第 4 个位置，也就是索引为 3 的位置。还有另外一个数是 888 ，但是 888 并没有出现在数组中，所以返回 -1 。
但是呀，大家有没有发现，这个程序看着虽然是实现了，但它还好像又有很多存在的新问题。是什么呢？
当前存在的问题是，我们只能在一个 int 型的数组中查找一个 int 型的元素。但是在 java 语言中，单单基本类型就有8种。更不用提，我们用户还可以自己创建各种各样的类，每个类都可以看作是一个新的类型。那我们就更不可能去每个类都写一个 search 方法对吧。
因此，对于这样子的问题？我们要如何解决呢？
这个时候我们要使用到 java 语言中的泛型。接下来我们将依据泛型来进行改造升级。
3、使用泛型
在这里，我们先简单的复习一下 java 的基本数据类型。具体如下：
- 在
java语言中的泛型，只能接受类对象，而不能接受基本数据类型。 java中的8中基本数据类型为：boolean、byte、char、short、int、long、float和double。- 由于泛型只能接受类对象，因此，为了应对这种状况，
java语言对每一种基本数据类型都做了一个对应的包装类。那么这些数据类型和他们所对应的包装类之间，可以进行相互的转换。其中，8种对应的包装类分别为：Boolean、Byte、Character、Short、Integer、Long、Float和Double。 - 有了包装类的概念，那么在使用泛型的时候，如果我们想传入的类型是上面第①点中的基本数据类型，最终只需要将这些数据类型转换成它们的包装类即可使用。
4、升级改造
上面我们简单了解了 java 语言中泛型的一些基本信息，那现在，我们用所学到的泛型，来改造原先例子里的代码。具体代码如下：
public class LinearSearch {
private LinearSearch() {
}
// 静态方法
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;
}
public static void main(String[] args) {
Integer[] data = {
24, 45, 67, 12, 465, 78, 68};
int res = LinearSearch.search(data, 12);
System.out.println(res);
int res2 = LinearSearch.search(data, 888);
System.out.println(res2);
}
}
此时，控制台的输出为：
3
-1
通过这种方式，我们让这个算法的灵活性又加强了一点点。
5、使用自定义类
上面我们对线性查找有了基础的了解，现在，大家来思考一个问题：我们是否可以自己设计一个 Student 类，这个类里面呢，有什么样的成员变量都无所谓，之后呢，基于 Student 类的设计，自己定义这个类里面的 equals 函数。
接下来将依据上面这个题目来进行代码编写：
首先在项目的 src 目录下新建一个 Student 类，具体代码如下：
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.equals(another.name);
}
}
接下来，继续改造上面的 LinearSearch.java ，具体代码如下：
public class LinearSearch {
private LinearSearch() {
}
// 静态方法
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;
}
public static void main(String[] args) {
Integer[] data = {
24, 45, 67, 12, 465, 78, 68};
int res = LinearSearch.search(data, 12);
System.out.println(res);
int res2 = LinearSearch.search(data, 888);
System.out.println(res2);
Student[] students = {
new Student("Monday"),
new Student("Tuesday"),
new Student("Wednesday")};
Student tuesday = new Student("Tuesday");
int res3 = LinearSearch.search(students, tuesday);
System.out.println(res3);
}
}
现在，我们来看下控制台的输出结果：
3
-1
1
大家可以看到，上面输出的依然是 3 和 -1 。最后一个输出的 1 ，是我们自定义的 Student 类所输出的结果。这样看来，整个程序的灵活性又增强了。
6、循环不变量
继续，我们依旧根据线性查找这个算法，来学习循环不变量。循环不变量这个概念，听起来似乎有点理论。但实际上，当我们在使用算法时，如果能够很好的运用这个概念，无论是对算法的理解，还是真正在写算法的时候，都能够使得我们更加容易地写出正确的算法。
循环，是程序设计中非常重要的一种构建逻辑的方式。实际上，大家在设计算法的时候，近乎所有的算法都会有循环这个概念。我们总是要循环地去做一件事情，逐渐地把我们当下在求解的算法给求解出来。
比如说，对于下面这个最简单的线性查找法：
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;
}
那上面这个算法的循环不变量指的是什么呢？指的是 for(int i = 0; i < data.length; i++) 这一串。
所谓循环不变量，指的是在每一轮开始的时候，循环的条件是不变的。大家可以想象一下，每回 if 语句如果在执行时无法在 data[i] 中匹配具体 target 的值，那么就会接着继续下一个 for 循环，而这个 for 循环所执行的内容一直都是在 [0…i) 这个区间内，因此称它为循环不变量。
在上面的这段算法中，其中的一段代码：
if(data[i].equals(target))
return i;
这段代码称为是循环体，主要作用是维持循环不变量。
三、📊算法复杂度
下面，我们来讲一下算法的复杂度。
1、简单的复杂度分析
我们为什么要对算法做复杂度分析呢，其实是为了用来表示算法的性能。
比如说，对于同样的任务，我们将会有不同的算法来完成这个任务，而不同的算法在时间性能上也有一定的差异，因此我们需要对算法做复杂度分析，来求解出最优的算法。
复杂度描述的是，随着数据规模 n 的增大，算法性能的变化趋势。
2、常见算法复杂度
下面，我们来看集中常见的算法复杂度。
（1）遍历一个 n * n 的二维数组
具体算法代码如下：
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
// 遍历到 A[i][j]
上面这个算法的时间复杂度为 O(n²) 。
（2）遍历一个 a*a 的二维数组
其中，a * a = n ，具体算法代码如下：
for(int i = 0; i < a; i++)
for(int j = 0; j < a; j++)
// 遍历到 A[i][j]
上面这个算法的时间复杂度为 O(a * a) ，也就是 O(n) 。在这种场景下，我们要明确 n 是谁。
（3）数字n的二进制位数
具体算法代码如下：
while(n) {
n % 2 // n 的二进制中的一位
n /= 2；
}
对于这个算法来说，其时间复杂度为 O(log2n) ，那如果是要算 n 的十进制位数呢？其时间复杂度为 O(log10n) 。但值得注意的是，不管是 以 2 为底还是以 10 为底的算法复杂度，都统一为 O(logn) 。因为在程序的算法中，这个底的差别对实际的算法并没有特别大的影响，所以都统称为 O(logn) 的复杂度。
3、复杂度总结
下面对常见几种算法的复杂度进行总结：
O(1) < O(logn) < O $\sqrt{n}$ < O(nlogn) < O(n²) < O(2n)< O(n!)
4、空间复杂度
当谈到时间复杂度时，我们还会不由自主的想起空间复杂度。但对于现代的计算机来说，硬盘存储容量越来越大，这个时候，空间复杂度就显得没有那么重要了。所以我们通常通过空间换时间的方式，来让程序得以更优解。
四、🗂️测试算法性能
依然以上面我们讲到的 LinearSearch 为例，接下来我们来测试算法性能。显然，在上面的算法中，只有 10 位数左右，但是在实际的开发中，计算量肯定是不止这么小的。一般是小到十万级，大到千万级和亿万级不等。接下来我们用上面的例子来进行改造，首先，在 src 目录下，新建一个 ArrayGenerator 的 java 类，具体代码如下：
public class ArrayGenerator {
private ArrayGenerator() {
}
public static Integer[] generateOrderArray(int n) {
Integer[] arr = new Integer[n];
for(int i = 0; i < n; i++)
arr[i] = i;
return arr;
}
}
接着，我们来改造 LinearSearch 这个类，具体代码如下：
import java.lang.reflect.Array;
public class LinearSearch {
private LinearSearch() {
}
// 静态方法
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;
}
public static void main(String[] args) {
// 想要取出的数据规模
int[] dataSize = {
1000000, 10000000};
for(int n: dataSize) {
Integer[] data = ArrayGenerator.generateOrderArray(n);
long startTime = System.nanoTime();
// 运行 100 次的时间
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');
}
}
}
此时，控制台的显示结果为：
n = 1000000, 100 runs : 0.3463959s
n = 10000000, 100 runs : 3.3792709s
大家可以看到，当 n 是 100万 的数据时，最终运行时间大约为 0.3s ，而当数据为 1000万 时，最终运行的时间大约为 3.3s 。它们两者之间的差距，大约是 10 倍左右，也就是说，呈线性增长。
五、📆 结束语
再上面的文章中，我们学习到了算法的基本知识，同时，还了解了线性查找法的基本思想。在此基础上，简单实现了线性查找法，并使用泛型和自定义类升级改造了线性查找法。
最后，我们还简单介绍了算法的复杂度分析，以及对我们所写的算法进行了性能测试。
到这里，关于本文的介绍就结束啦！不知道大家对线性查找法是否有一个更深的了解呢？
🐣彩蛋 One More Thing
- 关注公众号 星期一研究室 ，第一时间关注学习干货，更多精选专栏待你解锁~
- 如果这篇文章对你有用，记得留个脚印jio再走哟~
- 我们下期见！🔑🔑🔑
