子陣大小的隨機選擇

Question

我在做一個在線課程有以下選擇題：

，其中隨機選擇算法（基於快速排序）描述如下：

由於所有的多項選項都是線性函數a（我的意思是希臘字母alpha），所以我試圖通過考慮極限情況一個 = 0.5和通過消除判斷出正確答案一個 = 1

現在，如果一個 = 1，我們正在尋找「的概率是第一次迭代後的大小子陣列，其中你正在尋找的元素是原始數組」的大小< = 1次。在我看來，這總是正確的，因爲一次迭代總是減少問題的大小，所以概率應該是1.

如果我對此正確，這隻留下一個可能的正確答案，2 a - 1，但是，如果我填一個 = 0.5到這個表達我得到零，這沒有任何意義對我說：那就意味着它是不可能的問題的規模小於原來的問題大小的一半後一次迭代。

總之，所有這些答案似乎正確的我。有人能指出我推理中的缺陷嗎？

Answer 1

我不得不更仔細地閱讀這個問題：我們不是在尋找數組中的任何元素，而是中位數元素。因此，如果在第一次迭代導致不平衡分裂，中位元件總是會在較大的子陣列，所以P（0.5）= 0，證實了P（一個）= 2 一個 - 1答案。