algorithm - 比较顺序搜索和二分搜索

Question

假设我有一个未排序的实数数组，长度为 N。我想找到最大的非正数y，然后是数组中第一个小于y的数x，第一个数z 大于 y。

我想从理论上比较顺序搜索和非渐近二分搜索(即不仅仅是大操作系统)来找到这些值。声明是否合理:

• 顺序搜索要求
  • 0 排序比较，
  • 3*N 搜索比较(三个顺序搜索)。
• 二分查找要求
  • 2*N*ln(N) ≈ 1.39*N*log_2(N) 排序比较 ( quicksort, average ),
  • 最多 log_2(N) 次搜索比较(只有一次搜索，因为数组已排序，因此我们可以查看已排序数组中的相邻值以找到 x和 z 一旦我们找到 y)。

因此，我可以说二分查找会更快吗

1.39*N*log_2(N) + log_2(N) < 3*N 
<=> 
0 < N < 3.44779

即仅适用于极小的阵列？

Answer 1

是的，你的结论是正确的。然而，通常使用排序数组(或任何其他有组织的结构)的要点是当您只执行一次或很少执行预处理步骤时 - 与频繁查询相反。经过多次查询后，预处理成本得到了返回。