算法中的「哨兵」到底是啥？怎麼用？

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，這樣會提升算法的執行效率。

閱讀更多 人工智能channel 的文章

關鍵字: 技術 FLAG 維基百科