算法优化|说说哨兵(sentinel value)

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是要查找的目标元素。

下面给出一个基本算法：

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

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

03

带哨兵的线性搜索

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

基本算法思路：

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

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

以上，哨兵作用的一个简单典型的例子，如有疏漏，请指正。

更多文章：

动态规划|相邻约束下的最优解(House Robber II )

Numpy|需要信手拈来的功能

SQL|语句执行逻辑

Python|继承，多态，鸭子类型

Tensorflow|通过Variable及assign()感悟一点设计之道