java实现查找算法(一)：线性查找，折半查找

一  线性查找

public class LSearch
{
 public static int[] Data = { 12, 76, 29, 22, 15, 62, 29, 58, 35, 67, 58,
   33, 28, 89, 90, 28, 64, 48, 20, 77 }; // 输入数据数组

 public static int Counter = 1;    // 查找次数计数变量

 public static void main(String args[])
 {

  int KeyValue = 22;
  // 调用线性查找
  if (Linear_Search((int) KeyValue))
  {
   // 输出查找次数
   System.out.println("");
   System.out.println("Search Time = " + (int) Counter);
  }
  else
  {
   // 输出没有找到数据
   System.out.println("");
   System.out.println("No Found!!");
  }
 }

 // ---------------------------------------------------
 // 顺序查找
 // ---------------------------------------------------
 public static boolean Linear_Search(int Key)
 {
  int i; // 数据索引计数变量

  for (i = 0; i < 20; i++)
  {
   // 输出数据
   System.out.print("[" + (int) Data[i] + "]");
   // 查找到数据时
   if ((int) Key == (int) Data[i])
    return true; // 传回true
   Counter++; // 计数器递增
  }
  return false; // 传回false
 }
}

运行结果：
       [12][76][29][22]
       Search Time = 4


二 折半查找

public class BSearch
{
 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 = 22;
  // 调用折半查找
  if (BinarySearch((int) KeyValue))
  {
   // 输出查找次数
   System.out.println("");
   System.out.println("Search Time = " + (int) Counter);
  }
  else
  {
   // 输出没有找到数据
   System.out.println("");
   System.out.println("No Found!!");
  }
 }

 // ---------------------------------------------------
 // 折半查找法
 // ---------------------------------------------------
 public static boolean BinarySearch(int KeyValue)
 {
  int Left; // 左边界变量
  int Right; // 右边界变量
  int Middle; // 中位数变量

  Left = 0;
  Right = Max - 1;

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

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


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

评论

1 楼 hhlwork 2011-10-21