本站首页 返回顶部 关于博主

折半查找在故障排查中的应用

PDF版

       在计算机科学中,有种算法叫折半查找。对于有序的一组数据,它是一种性能很好地查找算法。

       算法很简单,对于有序的数组,搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,跟开始一样从中间元素开始比较,直到最好找到期望的元素。

       折半查找是计算机科学中的算法,在日常生活或工作某些场景的故障排查中也有用武之地。

       假设这样一种场景,某一件事情有 n 个步骤,这 n 步骤是串行的,第 n 个步骤的输入是第 ( n -1 ) 个步骤的输出, 即每个步骤的输入依赖前一个步骤的输出。对于已知的输入,每个步骤的输出是可以预知的。那么,如果第 1 个步骤的输入是正确的,最后一个步骤,即第 n 个步骤的输出是错误的,我们怎样排查问题最节省时间呢?

       下图是 n = 6 的例子。

       比较常见的方法是从步骤1 开始检查,如果步骤 1 的输入和输出都正确,那么检查步骤 2,直到发现某个步骤的输入正确,输出不正确,那么肯定是这个步骤有问题。这种方法,最好的情况需要查 1 次,最坏的情况需要查 6 次。

       如果采用折半查找,最好的情况需要查 1 次,最坏的情况需要查 3次。

       当然,以上列举的例子是所有步骤中只有一个步骤出错的情况。如果可能有 1 到多个步骤出错,折半查找的排查效率仍旧比顺序查找好。在最坏的情况下,如果所有步骤全部有错,折半查找的效率与顺序查找的效率是一样的。




请你留言