BFPRT算法解決的問題十分經(jīng)典，即從某n個元素的序列中選出第k大（第k蟹悦铩）的元素，通過巧妙的分 析隧期，BFPRT可以保證在最壞情況下仍為線性時間復(fù)雜度。
該算法的思想與快速排序思想相似宏蛉，當(dāng)然性置，為使得算法在最壞情況下，依然能達(dá)到o(n)的時間復(fù)雜 度嗅义，五位算法作者做了精妙的處理
算法步驟：
1. 將n個元素每5個一組篡石，分成n/5(上界)組凰萨。
2. 取出每一組的中位數(shù)，任意排序方法武通，比如插入排序珊搀。
3. 遞歸的調(diào)用selection算法查找上一步中所有中位數(shù)的中位數(shù)，設(shè)為x囚枪，偶數(shù)個中位數(shù)的情況下設(shè)定為選取中間小的一個链沼。
4. 用x來分割數(shù)組沛鸵，設(shè)小于等于x的個數(shù)為k，大于x的個數(shù)即為n-k疾捍。
5. 若i==k栏妖，返回x；若i<k咙鞍，在小于x的元素中遞歸查找第i小的元素趾徽；若i>k，在大于x的元素中遞歸查找第i-k小的元素疲酌。
終止條件：n=1時了袁，返回的即是i小元素。
圖解
Paste_Image.png
線性查找就是從數(shù)組的起始位置a[0]開始依次比較數(shù)組中的每一個值直到找到目標(biāo)值粥诫，當(dāng)然也有可能循環(huán)遍歷了數(shù)組中所有值也沒找到目標(biāo)值怀浆。
代碼
public class LinearSearchDemo {
public static void main(String[] args) {
int[] data = {2, 1, 4, 6, 12, 7};
int target = 12;
int searchIndex = search(data, target);
if (searchIndex != -1) {
System.out.println("found at: " + searchIndex);
}else {
System.out.println("not found");
}
}
/*
*@param data 待查找的數(shù)組
*@param target 待查找的值
*@return int 目標(biāo)值在數(shù)組中的索引执赡，如果沒找到返回-1
*/
public static int search(int[] data, int target) {
int length = data.length;
//從頭遍歷數(shù)組中的各個值函筋，如果找到目標(biāo)值就返回其索引
for (int i = 0; i < length; i++) {
if (data[i] == target) {
return i;
}
}
//代碼能走到這一步就說明上面的循環(huán)遍歷結(jié)束了也沒找到目標(biāo)值 //即目標(biāo)值不存在于數(shù)組中
return -1;
}
}
輸出結(jié)果：found at: 4