算法中的“哨兵”到底是啥?怎么用?
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,这样会提升算法的执行效率。
更多相关文章
- Linux Kernel(Android) 加密算法总结(二)- A netlink-based user-s
- Android(安卓)的缓存机制 Lrucache
- Android之RAS加密算法测试
- Android(安卓)实现SHA1加密算法代码
- 通过代码实例了解页面置换算法原理
- Android(安卓)内功心法(1.2)——android常用设计模式之工厂模式
- 2019AndroidBAT.字节跳动74道高级面试第二篇
- Android(安卓)Market排名算法及规则
- Android图像处理相关文章