随机子数组大小 select
Subarray size in randomized select
我正在做一个包含以下多项选择题的在线课程：
其中RANDOMIZEDSELECT算法（基于快速排序）描述如下：
因为所有的多项选择选项都是 a 的线性函数（我指的是希腊字母 alpha），我试图通过考虑消除来确定正确答案极限情况 a = 0.5 和 a = 1.
现在如果a = 1，我们正在寻找"the probability that after the first iteration the size of the subarray in which the element you are looking for is <=1 times the size of the original array"。在我看来，这总是正确的，因为一次迭代总是会减少问题的大小，所以概率应该是 1。
如果我对此是正确的，则只剩下一个可能的正确答案，2 a - 1。但是，如果我填写 a = 0.5 进入这个表达式我得到零，这对我来说没有意义：这意味着问题大小不可能在一次迭代后小于原始问题大小的一半。
简而言之，none 这些答案对我来说似乎是正确的；有人可以指出我推理中的缺陷吗？
我不得不更仔细地阅读问题：我们不是在寻找数组的任何元素，而是在寻找 中位数 元素。因此，如果第一次迭代导致分裂不平衡，则中值元素将始终位于较大的子数组中，因此 P(0.5) = 0，确认 P(a) = 2 a - 1 个答案。
我正在做一个包含以下多项选择题的在线课程：
其中RANDOMIZEDSELECT算法（基于快速排序）描述如下：
因为所有的多项选择选项都是 a 的线性函数（我指的是希腊字母 alpha），我试图通过考虑消除来确定正确答案极限情况 a = 0.5 和 a = 1.
现在如果a = 1，我们正在寻找"the probability that after the first iteration the size of the subarray in which the element you are looking for is <=1 times the size of the original array"。在我看来，这总是正确的，因为一次迭代总是会减少问题的大小，所以概率应该是 1。
如果我对此是正确的，则只剩下一个可能的正确答案，2 a - 1。但是，如果我填写 a = 0.5 进入这个表达式我得到零，这对我来说没有意义：这意味着问题大小不可能在一次迭代后小于原始问题大小的一半。
简而言之，none 这些答案对我来说似乎是正确的；有人可以指出我推理中的缺陷吗？
我不得不更仔细地阅读问题：我们不是在寻找数组的任何元素，而是在寻找 中位数 元素。因此，如果第一次迭代导致分裂不平衡，则中值元素将始终位于较大的子数组中，因此 P(0.5) = 0，确认 P(a) = 2 a - 1 个答案。