線性查找算法(BFPRT)

BFPRT算法的作者是5位真正的大牛（Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan）。

BFPRT解決的問題十分經典，即從某n個元素的序列中選出第k大(第k小)的元素，通過巧妙的分析，BFPRT可以保證在最壞情況下仍為線性時間複雜度。

将n個元素每 5 個一組，分成n/5(上界)組。

取出每一組的中位數，任意排序方法，比如插入排序。

遞歸的調用 selection 算法查找上一步中所有中位數的中位數，設為x，偶數個中位數的情況下設定為選取中間小的一個。

用x來分割數組，設小于等于x的個數為k，大于x的個數即為n-k。

若i==k，傳回x；若i<k，在小于x的元素中遞歸查找第i小的元素；若i>k，在大于x的元素中遞歸查找第i-k 小的元素。

　終止條件：n=1 時，傳回的即是i小元素。

ps:

1.為何利用5作為元組大小，可能是與寄存器的數量和運算有關。

2.為何稱為線性的解答：

劃分時以5個元素為一組求取中位數，共得到n/5個中位數，再遞歸求取中位數，複雜度為T(n/5)。

得到的中位數x作為主元進行劃分，在n/5個中位數中，主元x大于其中1/2*n/5=n/10的中位數，而每個中位數在其本來的5個數的小組中又大于或等于其中的3個數，是以主元x至少大于所有數中的n/10*3=3/10*n個。同理，主元x至少小于所有數中的3/10*n個。即劃分之後，任意一邊的長度至少為3/10，在最壞情況下，每次選擇都選到了7/10的那一部分，則遞歸的複雜度為T(7/10*n)。

在每5個數求中位數和劃分的函數中，進行若幹個次線性的掃描，其時間複雜度為c*n，其中c為常數。

其總的時間複雜度滿足： T(n)<=T(n/5)+T(7/10*n)+c*n

假設T(n)=x*n，其中x不一定是常數（比如x可以為n的倍數，則對應的T(n)=O(n^2)）。則有 x*n <= x*n/5 + x*7/10*n + c*n。得到 x<=10*c

于是可以知道x與n無關，T(n)<=10*c*n，為線性時間複雜度算法。

而這又是最壞情況下的分析，故BFPRT可以在最壞情況下以線性時間求得n個數中的第k個數。