algorithm - 二分搜索与三元搜索

Question

就时间和空间复杂度而言，二分查找是否优于三元查找？

Answer 1

两者都有恒定的空间，但是三元搜索的大 O 时间是 Log_3 N 而不是二分搜索的 Log_2 N ，因为 log_b(N) = log_x(N)/log_x(b) 两者都出现 log(N)。

在实践中不使用三元搜索，因为您必须在每个步骤中进行额外的比较，这在一般情况下会导致更多的比较。2 * Log_3(N) 比较与 Log_2(N) 比较。

Answer 2

这可能取决于数据。如果您有大致相等的小于、等于和大于比较数，那么将数据分成三种方式意味着对数的底数是 3 而不是 2，这更好。但在实践中，三路比较比二路比较更昂贵，因此在一般情况下，三路比较的额外成本可能不值得。