算法中的“哨兵”到底是啥？怎么用？

发布于：2021-12-20 08:57:15  栏目：技术文档

　　01

　　哨兵

　　先看下维基百科对其定义：

　　In computer programming, a sentinel value (also referred to as a flag value, trip value, rogue value, signal value, or dummy data) is a special value in the context of an algorithm which uses its presence as a condition of termination, typically in a loop or recursive algorithm.

　　简单来说，哨兵是在循环或迭代算法中用来标志终止条件的值。

　　下面看下一个典型的哨兵用法的例子。

　　02

　　线性搜索

　　线性搜索是指在给定数组中从头搜索，直到找到一个与target相等的索引。Li是数组中索引为i的元素，T是要查找的目标元素。

　　下面给出一个基本算法：

　　Set i to 0.If Li=T, the search terminates successfully; return i.Increase i by 1.If i < n, go to step 2. Otherwise, the search terminates unsuccessfully.

　　上面的算法，如何用哨兵进行优化呢？

　　03

　　带哨兵的线性搜索

　　添加一个元素Ln（也就是哨兵）到数组中，假如初始数组中没有查找到T元素，则搜索将会到达哨兵处。

　　基本算法思路：

　　Set i to 0.If Li=T, go to step 4.Increase i by 1 and go to step 2.If i < n, the search terminates successfully; return i. Else, the search terminates unsuccessfully.

　　可以看到，加入哨兵后，每次不用去检查是否 i < n，这样会提升算法的执行效率。

相关推荐