algorithm - 一个关于二分查找的问题

Question

为什么人们通常做二分搜索而不是三重搜索(划分每次排列成三份)甚至每次分成十份？

Answer 1

因为二分查找的比较和查找次数最少。为了简单的直觉，考虑每次分成 4 个部分。

[         |         |    .    |         ]
          v1        v2        v3

您现在已经完成了 3 次查找，并且必须将您搜索的最差值与所有三个值进行比较。将此与二进制搜索的两次迭代进行比较:

[                   |    .              ]
                    v1
[                   |    .    |         ]
                    v1        v2

您现在已经将搜索范围缩小了相同的数量，但只进行了 2 次查找和 2 次比较。