【经典算法学习-排序篇】顺序查找

文章目录 请放心食用

一、什么是算法

1.算法的定义

2.一些补充的概念

二、顺序查找

1.元素怎么查

2.顺序查找

3.时间复杂度分析

4.代码优化

 三、总结

四、课后小练习

 五、下期预告

一、什么是算法

算法，是一种高深的学问。或许有人说，算法，就是几个字母，algorithm。不得不说这也对

不过，这样的理解不免得有些浅显。我们不妨换一种说法：

1.算法的定义

在一篇经典的教材《Introduction.to.Algorithms》的开篇，这样写道：

Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.

(非正式地说，算法是任何定义明确的计算过程，它将某些值或一组值作为输入，并产生某些值或值组作为输出。因此，算法是将输入转换为输出的一系列计算步骤。)

 在这段文字里，我们看到的最多的两个词语就是：输入和输出。这时候又会有人说：

A:啊哈，算法就是这种东西？输入，不就是什么cin，scanf这些吗？输出，不就是cout，printf这类的吗？顶多，再用个read()这类的快读不是吗？算法可真简单！

B:啊对对对，啊对对对，阿对对对！（我可不会说我是在水字数）

 看的简单一点，这段话就是这个意思。但是，我们如果看的深远一点，那么就是：算法是一种解决问题的工具，我们只需要把输入数据和输出数据描述清楚了，我们的算法就能够实现。这也是说我们的算法要明确我们有什么、要什么。

2.一些补充的概念

• 数据结构

在实现一个算法的时候，我们大部分时候都会用到一种东西：数据结构。在实现同一种算法的时候，我们如果使用不同的数据结构，那么我们得到的效率（例如时间复杂度、空间复杂度等）也会截然不同。

我们不妨举个例子：以我们最熟悉的排序为例。我们可以使用数组，实现冒泡排序、桶排序、插入排序；我们也可以使用树来实现树型排序；我们还可以使用一堆变量来实现啥也不是排序······

数据结构不同，效果截然不同。我们在日常中常见的数据结构包括：数组、链表、树、队列、栈、图等等。

• 算法效率

在我们实现一个算法的时候，我们需要考虑到这个算法的效率问题，简称算法效率。

我们如何判断一个算法的好坏？我们就是通过算法效率来判断的。一个好的算法，可以大幅减少程序的使用时间和资源消耗。

那么，我们如何判断（计算）算法的效率呢？我们不需要进行精确的计算（虽然也可以进行精确计算，只不过没有必要），只需要引入时间复杂度和空间复杂度两个概念就可以解决。综合评估两个复杂度以达到最优，就能实现估算算法效率的好坏了。

• 时间复杂度

我们将算法中基本操作重复执行的频率称为时间复杂度（基本操作一般指程序中最深层循环中的语句，一般包括一些赋值语句、运算语句等）。

一般的，时间复杂度和程序中的循环息息相关。循环的层数越多，那么程序的时间复杂度就越高；循环的层数越少，那么程序的时间复杂度就越低。这也是我们为什么说暴力枚举的时间复杂度贼高。

怎么计算时间复杂度？对于每一个程序，我们等可以将其转化为常数或与n相关的函数表达式，记作f(n)。我们如果把每一段程序所花费的时间相加，就会得到一个非常复杂的表达式，在合并的时候保留量级最大的部分就可以确定时间复杂度了，记作O(f(n))。这里的O就是代表数量级。

常见的时间复杂度有：O(1)，O()，O(n)， O()，O()，O()，O()，O(n!)等。

• 空间复杂度

空间复杂度，顾名思义，就是程序从开始执行到结束所用的内存容量，即整个的过程需要用到多少内存容量 。为了更好的评估算法的本身，我们在计算的时候将输入的数据排除在外。在计算时，我们更考虑算法在运行的时候需要额外定义多少的变量（存储结构）。

例如，我们如果要实现一个两数相加的程序，那么所用的空间复杂度为O(1)。

二、顺序查找

1.元素怎么查

查找元素，又称为检索，如果找到满足条件的数，那么就是查找成功，反之则是查找失败。

怎么查找？查找的方式多种多样，我们以一道例题为例，来给大家详细讲解。

【深基4.例2】找最小值 - 洛谷

•  顺序查找

顺序查找，也称为线性查找。我们从数组的一边开始，逐个查找。如果和目标元素相同，则查找成功。反之如果没有找到目标元素，那么就查找失败。

//样例代码-顺序查找
#include 

using namespace std;

int a[1001], n;
int _max;

int main()
{
	cin >> n;
	for(int i=0;i> a[i];
	}
	for(int i=0;i 
折半查找
折半查找，即二分查找，也就是我们常说的“二分法”。这是一种效率较高的代码。算法的核心是每一次搜尽可能的缩小搜索空间。我们会在后面的文章中提到的。
 
索引查找
索引查找，主要分为基本索引查找和分块查找。对于无序的一组数，建立索引表，使索引表或分块有序，结合顺序查找，已完成搜索。这个我们后文提到。
 
随机查找
啊这，这还是算了吧。懂得都懂啊，这不是个算法~
 
2.顺序查找 
 
 
例题1：查找3
 
 
给定一组长度为n的数字序列，寻找这组序列是否有“3”这个数字。如果有，则输出数字3的下标；若没有，则输出-1。若一组序列中出现多个相同的数字，则优先输出靠前的下标。
 
 
【输入】
 
 
第一行一个数字n，代表序列长度。
 
 
第二行，输入该序列。
 
 
【输出】
 
 
输出数字3所在的下标，若未查找到则输出-1。
 
 
【输入样例#1】
 
 
5
 
 
5 4 3 2 1
 
 
【输出样例#1】
 
 
2
 
 
【输入样例#2】
 
 
5
 
 
7 5 4 6 9
 
 
【输出样例#2】
 
 
-1
 
 
【数据规模与提示】
 
 
 
 
第一步：输入数字
 
这一步没啥可说的，就按照题意来写就行了呗。
 
#include 

using namespace std;

int main()
{
    int n;
    int a[101]; // 由于n的规模最大到100，所以申请101长度，不过分吧？
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    return 0;
}
 
第二步：顺序查找
 
这里就是关键：怎么查？
 
前文说过，顺序查找就是线性查找，从数组的一边开始逐个查找。那么，我们就来试试吧。
 
首先，我们需要考虑到，我们需要一个循环。
 
for (int i = 0; i < n; i++)
 
循环体会是什么？判断是否为3。如果不是3，就continue，继续查找。如果是的话，就输出这个下标，return出去。我们不妨写出来这段代码：
 
for (int i = 0; i < n; i++)
{
    if (a[i] != 3)
    {
        continue;
    }
    else
    {
        cout << i << endl;
        return 0;
    }
}
 
第三步：拼接
 
我们将主要的代码写完之后，就需要完成代码拼接工作了。拼接完成后，代码如下：
 
#include 

using namespace std;

int main()
{
    int n;
    int a[101]; 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++)
    {
        if (a[i] != 3)
        {
            continue;
        }
        else
        {
            cout << i << endl;
            return 0;
        }
    }
    cout << "-1" << endl;
    return 0;
}
 
3.时间复杂度分析 
 
最优情况
 
最优的情况，也就是说所有能不被执行的代码都不会被执行以达到最优。什么时候会产生最优？当序列中的第一个数字就是3时，此时的情况便是最优的。所以，最优情况为O(1)。
 
像这段代码的最优情况这样的是很少见的。大多数的代码的最优情况也仅仅是O(n)而已。
 
 
最差情况
 
这是我们最不愿意看到的情况了。但是，我们还是需要考虑。当循环被完全拉满，却一个3都没有找到的时候，此时便是最差的情况了。
 
在这种情况下，循环被执行满了。所以，此时的时间复杂度也就顺理成章的成为O(n)了。
 
 
平均情况 
 
综合最优情况和最差情况，时间复杂度为：
 
 这样的时间复杂度不算特别高，所以这段代码不用做什么优化了。
 
4.代码优化 
那么，如果我们真的要优化的话，如何优化？
 
我们不妨回顾我们的代码。我们的for循环每一次都要对数组是否越界而判断。这样的判断是否可以省去？如何省去？
 
我们可以使用一个while循环来解决。我们用脑洞来想到了这段代码：
 
（仔细想想，还真的是妙呀！）
 
int i = n;
while (a[i] != 3)
{
    i--;
}
cout << i << endl;
 
这段代码优化后，本质上时间复杂度没有改变。所以，此处优化的作用不是很大，但是优化后可能会产生一些微小的效果。
 
附上优化后的全部代码：
 
#include 

using namespace std;

int main()
{
    int n;
    int a[101];
    cin >> n;
    int i = n;
    while (a[i] != 3)
    {
        i--;
    }
    cout << i << endl;
    return 0;
}
 
 三、总结 
代码是否优化，我们使用的方法却是一致的——顺序查找，又称为线性查找。
 
线性查找的中心思想其实就是逐个寻找，直到找到目标。这就有些类似于暴力枚举的思想。
 
线性查找作为我们代码中最常用的查找方式，如今也是被广泛使用。学好线性查找，你就已经能够解决所有关于查找类的问题了。
 
四、课后小练习 
光听不练，怎行？
 
奉上今日的课后题单，各位大佬们一定要接受这份提题单！
 
求知若渴，虚心若愚。
 
 
 
有一门课不及格的学生 - 洛谷
 
 
不定方程求解 - 洛谷
 
 
[NOIP2002 提高组] 字串变换 - 洛谷（较难）
 
 
 五、下期预告 
顺序查找，太慢！这是什么东西，时间复杂度这么高！
 
我比你少一半的时间！大哥！
 
我把你砍了一半！
 
（猜猜下期讲什么）