java - 如果尝试对未排序的数据集进行二分查找，会发生什么情况？

Question

<分区>

Answer 1

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

编辑 为了好玩，我做了一个小实验。首先，我选择了一个数组大小并生成了一个 int 数组 {0, 1, ..., size-1}。然后我打乱了数组，对每个值 0、1、...、size-1 进行了二进制搜索，并计算找到了多少个。对于每种尺寸，我重复洗牌/搜索每个值步骤 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%

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