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

Question

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

Answer 1

结果是不可预测的.如果数据集具有目标,则可能找到也可能找不到.

编辑只是为了踢,我做了一个小实验.首先,我选择了一个数组大小并生成了一个int数组{0,1,...,size-1}.然后我改组了数组,对每个值0,1,......,size-1进行了二元搜索,并计算了其中有多少被发现.对于每个大小,我重复了shuffle/search-for-values值步骤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%

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