米尔嘉对理纱耳语几句，理纱随即开始敲击键盘。说起来理纱打字真是快啊，而且打字的时候基本没有什么声音——无声地输入。

过了一会儿，完成输入的理纱给我们展示“ 带有哨兵的 顺序查找算法”。

我们全都盯着笔记本电脑屏幕，苦苦思索着。

看了好一会儿，泰朵拉叫道：“不动笔的话怎么也弄不明白！”接着就在笔记本上写了起来。看来泰朵拉计算机启动了。

“通过测试用例来具体算一下吧。”米尔嘉说。

逐行调试带有哨兵的顺序查找算法

（输入为 ）

“通过逐行调试发现，S4→ S5→ S6这三行在不断地循环。”泰朵拉说，“感觉带有哨兵的顺序查找算法在判断条件时比普通的顺序查找算法简单很多啊……对了，哨兵到底指什么？”

“指的是在S2行放在 中的数。”米尔嘉回答，“只要把 放在 中，当 时就一定能找到 ，因此，查找就不可能越过这里继续进行。为了防止不小心运行过头而设置的数，这就是哨兵，英文为sentinel。有哨兵存在的话，在S4的 处便不再需要确认 的范围。”

“之前的LINEAR-SEARCH算法的运行步数是18，这次的SENTINEL-LINEAR-SEARCH算法的运行步数是16。可以说是稍微……变快了点吧，但是仅仅节约了两步呀……”

“这只是个示例。我们需要将行S4的运行次数设为 ，将 设为‘能找到 ’的指示器，一般化地求带有哨兵的顺序查找算法的运行步数。”

带有哨兵的顺序查找算法的运行步数

• ，表示能找到 的情况。
  此时 等于 在数列中的位置
• ，表示无法找到 的情况。
  此时 等于

带有哨兵的顺序查找算法的运行步数

“普通的顺序查找算法的运行步数是 。”泰朵拉一边看着笔记本一边说，“而带有哨兵的顺序查找算法的运行步数是 ！”

“原来如此！”我喊出声来，“只要用数学公式来表示运行步数，就能比较算法的速度了。”

“要比较对吧！我来写不等式！”泰朵拉说。

“用不等式直接比较二者的大小当然没有问题。”我说，“不过还可以采用一种常规方法 : 计算‘左边 - 右边’这个式子，判断它的结果是否大于0。”

顺序查找算法的运行步数 - 带有哨兵的顺序查找算法的运行步数

“哦哦……”泰朵拉说。

“因此，只要 ，我们就能认为带有哨兵的顺序查找算法更快。”我说。用数学公式表达思路，真是让人放心啊。

“ 等价于 。如果 在数列 中第一次出现的位置在3之后，带有哨兵的顺序查找算法就会更快。”

“原来用数学公式表达后还能有这样的发现呀！”泰朵拉豁然开朗。

“‘无法找到 ’的情况是最耗时间的，顺序查找算法的运行步数是 ，带有哨兵的顺序查找算法的运行步数是 。这就是各个算法的 最大 运行步数吧。”我说。 rpZKh/waVNKyxPMIKTEPj0OxEEQYrozs3Lulz+ymnT/n0nnvdBg5kq0Jkhls02ue