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

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

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

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

       下图是 n = 6 的例子。

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

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

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

| 2020年3 月18日 星期三 19:59:31| 观点想法| 添加评论|