子阵大小的随机选择

Question

我在做一个在线课程有以下选择题：

，其中随机选择算法（基于快速排序）描述如下：

由于所有的多项选项都是线性函数a（我的意思是希腊字母alpha），所以我试图通过考虑极限情况一个 = 0.5和通过消除判断出正确答案一个 = 1

现在，如果一个 = 1，我们正在寻找“的概率是第一次迭代后的大小子阵列，其中你正在寻找的元素是原始数组”的大小< = 1次。在我看来，这总是正确的，因为一次迭代总是减少问题的大小，所以概率应该是1.

如果我对此正确，这只留下一个可能的正确答案，2 a - 1，但是，如果我填一个 = 0.5到这个表达我得到零，这没有任何意义对我说：那就意味着它是不可能的问题的规模小于原来的问题大小的一半后一次迭代。

总之，所有这些答案似乎正确的我。有人能指出我推理中的缺陷吗？

Answer 1

我不得不更仔细地阅读这个问题：我们不是在寻找数组中的任何元素，而是中位数元素。因此，如果在第一次迭代导致不平衡分裂，中位元件总是会在较大的子阵列，所以P（0.5）= 0，证实了P（一个）= 2 一个 - 1答案。