java实现查找算法(二)：费氏查找 ，插补查找

一 费氏查找

使用费氏数列  1 1 2 3  5 8 13 构成的数列，切割范围来进行查找

public class FSearch
{
 public static int Max  = 20;
 public static int[] Data = { 12, 16, 19, 22, 25, 32, 39, 48, 55, 57, 58,
   63, 68, 69, 70, 78, 84, 88, 90, 97 }; // 数据数组
 public static int Counter = 1;    // 计数器

 public static void main(String args[])
 {
  int FinA; // 费氏数

  FinA = 1; // 定义费氏数
  while (Fib(FinA) <= Max)
   FinA++;

  int KeyValue = 32;
  // 调用费氏查找
  if (FibonacciSearch(FinA, KeyValue))
  {
   // 输出查找次数
   System.out.println("");
   System.out.println("Search Time = " + (int) Counter);
  }
  else
  {
   // 输出没有找到数据
   System.out.println("");
   System.out.println("No Found!!");
  }
 }

 // ---------------------------------------------------
 // 递归求费氏级数
 // ---------------------------------------------------
 public static int Fib(int N)
 {
  if (N <= 1) // 递归结束条件
   return N;
  else
   return Fib(N - 1) + Fib(N - 2); // 递归执行部分
 }

 // ---------------------------------------------------
 // 费氏查找法
 // ---------------------------------------------------
 public static boolean FibonacciSearch(int n, int KeyValue)
 {
  int Root; // 左边界变量
  int Distance_1; // 上一个费氏数
  int Distance_2; // 上二个费氏数（差值）
  int Temp; // 数据暂存变量

  Root = Fib(n - 1);
  Distance_1 = Fib(n - 2);
  Distance_2 = Fib(n - 3);

  do
  {
   if (KeyValue < Data[Root - 1]) // 欲查找值较小
   { // 查找前半段
    Root = Root - Distance_2;
    Temp = Distance_1;
    Distance_1 = Distance_2;
    Distance_2 = Temp - Distance_2;
   }
   // 欲查找值较大
   else if (KeyValue > Data[Root - 1])
   { // 查找后半段
    Root = Root + Distance_2;
    Distance_1 = Distance_1 - Distance_2;
    Distance_2 = Distance_2 - Distance_1;
   }
   else if (KeyValue == Data[Root - 1]) // 查找到数据
   {
    System.out.println("Data[" + (Root - 1) + "] = "
      + Data[Root - 1]);
    return true;
   }
   Counter++;
  } while (Distance_2 >= 0);
  return false;
 }
}

运行结果：
    Data[5] = 32
    Search Time = 5

二 插补查找

类似于折半查找，不同的是插补查找使用的是按照比例来选择对比项

public class ISearch
{
 public static int Max  = 20;
 public static int[] Data = { 12, 16, 19, 22, 25, 32, 39, 48, 55, 57, 58,
   63, 68, 69, 70, 78, 84, 88, 90, 97 }; // 数据数组
 public static int Counter = 1;    // 计数器

 public static void main(String args[])
 {
  int KeyValue = 32;
  // 调用插补查找
  if (InterpolationSearch(KeyValue))
  {
   // 输出查找次数
   System.out.println("");
   System.out.println("Search Time = " + (int) Counter);
  }
  else
  {
   // 输出没有找到数据
   System.out.println("");
   System.out.println("No Found!!");
  }
 }

 // ---------------------------------------------------
 // 插补查找法
 // ---------------------------------------------------
 public static boolean InterpolationSearch(int KeyValue)
 {
  int Low; // 插补查找法左边界变量
  int High; // 插补查找法右边界变量
  int Middle; // 插补查找法中间数

  Low = 0;
  High = Max - 1;
  Middle = Low + (KeyValue - Data[Low]) * (High - Low)
    / (Data[High] - Data[Low]);

  if (Middle < Low)
   Middle = Low;
  if (Middle > High)
   Middle = High;

  while (Low <= High)
  {
   if (KeyValue < Data[Middle]) // 欲查找值较小
    High = Middle - 1; // 查找前半段
   // 欲查找值较大
   else if (KeyValue > Data[Middle])
    Low = Middle + 1; // 查找后半段
   // 查找到数据
   else if (KeyValue == Data[Middle])
   {
    System.out.println("Data[" + Middle + "] = " + Data[Middle]);
    return true;
   }

   if (Low < High)
    Middle = Low + (KeyValue - Data[Low]) * (High - Low)
      / (Data[High] - Data[Low]);
   if (Middle < Low)
    Middle = Low;
   if (Middle > High)
    Middle = High;

   Counter++;
  }
  return false;
 }
}

运行结果：
    Data[5] = 32
    Search Time = 2


原文网址：http://blog.csdn.net/myjava_024/archive/2008/11/19/3335548.aspx