BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分 析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。
该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂 度，五位算法作者做了精妙的处理
算法步骤：
1. 将n个元素每5个一组，分成n/5(上界)组。
2. 取出每一组的中位数，任意排序方法，比如插入排序。
3. 递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。
4. 用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。
5. 若i==k，返回x；若i<k，在小于x的元素中递归查找第i小的元素；若i>k，在大于x的元素中递归查找第i-k小的元素。
终止条件：n=1时，返回的即是i小元素。
图解
Paste_Image.png
线性查找就是从数组的起始位置a[0]开始依次比较数组中的每一个值直到找到目标值，当然也有可能循环遍历了数组中所有值也没找到目标值。
代码
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 待查找的数组
*@param target 待查找的值
*@return int 目标值在数组中的索引，如果没找到返回-1
*/
public static int search(int[] data, int target) {
int length = data.length;
//从头遍历数组中的各个值，如果找到目标值就返回其索引
for (int i = 0; i < length; i++) {
if (data[i] == target) {
return i;
}
}
//代码能走到这一步就说明上面的循环遍历结束了也没找到目标值 //即目标值不存在于数组中
return -1;
}
}
输出结果：found at: 4