数学女孩4：随机算法最新章节_结城浩著

2.1.3　顺序查找

顺序查找是查找算法中的一种，可以按顺序查找数列中是否存在特定的数。呃……虽然能查找的东西并不局限于数，但为了说明方便，这里我们来进行数的查找。

嗯，现在我来举个例子，比如说有这样一个数列。

${31,41,59,26,53\}$

在这5个数中……就假设我们要查找26这个数吧。要是由人来查找，只要看一眼就能够找到26。但是计算机先生只能一个一个地检查。顺序查找指的就是“从第一个开始按顺序来查找”这样一种算法。

遵循顺序查找算法来查找26的情形是这样的。

◎　　◎　　◎

“但是，这不是一目了然的嘛。”我说。

“没错，我一开始也是这么认为的。但是——”说到这，泰朵拉噗嗤一声笑了出来，“我们要从理所当然的地方开始思考问题……对吧？”

“……说得对。”

“我们要从理所当然的地方开始思考问题。”

这是我曾对泰朵拉说过的话，她记得真牢啊。

以前总是我给泰朵拉学妹讲课、回答数学疑问、协助解数学题。但是今天反了过来，我向泰朵拉请教，这让我有种新鲜的感觉。

“比如说，我们有100万个数。”泰朵拉像喷泉那样将双手“哗”地打开，“要是有那么多的数，即使是按顺序一个个检查这种简单的工作，人类也只能束手无策。但是，只要将算法转化为程序并输入到计算机中，计算机先生就能胜任这份工作。”

“诶……泰朵拉你学得好认真呐。说起来，泰朵拉你说过想从事计算机相关的工作呢——不过，我对算法的印象还是很模糊呀。”我说。

“那我们把顺序查找算法好好地总结归纳一下……”

泰朵拉一边说着，一边拿出一张卡片。

顺序查找算法（输入与输出）

输入

数列 $A={A[1],A[2],A[3],\cdots,A[n]\}$
数列的大小
要查找的数

输出

在中找到与相同的数时，

输出“能找到”。

在中未找到与相同的数时，

输出“无法找到”。

“我们进行顺序查找时……”泰朵拉解释说，“只要提供个数组成的数列 $A={A[1],A[2],A[3],\cdots,A[n]\}$ 以及数，便可以利用顺序查找算法从数列中找出。也就是说，输入是、还有。”

“嗯嗯。”我点点头，紧接着问道，“ A[1] ，指的就是 A_1 吗？”

“是的，没错。在这里代替数学上

$A_1,A_2,A_3,\cdots,A_n$

的写法，改用

$A[1],A[2],A[3],\cdots,A[n]$

这样的写法。 A[1] 表示数列中的第1个数。”

“嗯，我明白了。”我说。

“向顺序查找算法中输入数列、数列大小，以及要寻找的数。接下来……如果算法在中发现了与相等的数，则输出‘能找到’，未能发现时则输出‘无法找到’。也就是说，输出是‘能找到’或者‘无法找到’。”

“原来如此。输出是表示算法运算的结果呀。”

“嗯，是的。因此，顺序查找算法的流程就可以像这样表示。”

泰朵拉又拿出一张卡片。

顺序查找算法（流程）

“这里使用 伪代码 表示算法的流程。”

“伪代码？”

“嗯。伪代码不是真正的代码，而是一种形似程序的语言，英文是pseudocode。虽然计算机先生不能直接运行这种用伪代码表示的流程，但是用伪代码就可以以程序的形式表示算法了。”

“哦？”

“村木老师说‘不同的书表示算法的方法千差万别，但无论哪一种表示方法，都必须能明确表示出从输入到输出的各个步骤。’”

“原来如此……那么，这就是顺序查找算法了吧。”

“是的。用一句话来表示顺序查找算法就是‘按照 $A[1],A[2],A[3],\cdots,A[n]$ 的顺序判断是否有与相等的元素’。”

“从行L1开始看这个流程对吧？”

“嗯嗯。”泰朵拉不住地微微点头，并接着说道，“老师是这样说的，‘请运行行L1至行L10的各个步骤’。”

“运行……？”

泰朵拉重新看了看笔记本，慢慢地继续话题。

“嗯，按照村木老师的说法，先想象自己变成了计算机先生，然后再去运行代码会更好。

大喊‘我是计算机’
想象自己被给予了算法与输入
然后，按照流程笨拙、踏实地一步一步运行

不得不说这很麻烦，但据说这样是理解算法最快的方法。”

“是吗……”

“我要试试老师说的，我特别喜欢这种毅力定胜负的比拼。接下来，人家要变成计算机了！”

“真是台干劲十足的计算机呀。”我说道。

“泰朵拉计算机，启动。”理纱轻轻说道。

2.1.3 顺序查找

2.1.3　顺序查找