java - 如果尝试对未排序的数据集进行二分搜索会发生什么？

Question

如果尝试对未排序的数据集进行二分搜索会发生什么？

Answer 1

结果是不可预测的。如果数据集有目标，它可能找到也可能找不到。

编辑只是为了好玩，我做了一个小实验。首先，我选择了一个数组大小并生成了一个 int 数组 {0, 1, ..., size-1}。然后我打乱了数组，对每个值 0、1、...、size-1 进行了二进制搜索，并计算找到了多少。对于每种大小，我重复 shuffle/search-for-each-value 步骤 100,000 次，并记录成功搜索的百分比。（对于已排序的数组，这将是 100%。）结果是（四舍五入到最接近的百分比）：

Size    % Hit
 10      34%
 20      22%
 30      16%
 40      13%
 50      11%
 60      10%
 70       9%
 80       8%
 90       7%
100       6%

所以数组越大，不排序的效果越差。即使对于相对较小的阵列，结果也非常激烈。

Answer 2

Binary Search 是针对Sorted Array 的，如果在 Non-Sorted Array 上进行，那么结果肯定是不可预测和不可靠的。

Answer 3

二进制搜索依赖于被排序的数据。它在数组中选择一个元素并确定 1. 如果这是它正在搜索的元素 2. 如果它不是它正在寻找的元素，它可能在哪里找到该元素。

第二点依赖于对数据进行排序来做出决定。想象一个未排序的数据。仅通过将搜索键与我们选择的元素进行比较，我们将无法确定该元素可能出现的位置。

因此，二进制搜索无法在未排序的数据中始终如一地工作。

Answer 4

您几乎肯定找不到您一直在寻找的元素。如果数组大部分是排序的，那么你可能会很幸运。

该算法可以以某种概率检测到这一点的方式实现，但除非它对数组进行全面扫描，否则无法保证二进制搜索会检测到这种错误情况。