线性查找法(BFPRT)

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