一 线性查找
又称顺序查找，是从数组的第一个元素开始查找，直到找到待查找元素的位置，直到查找到结果。
最佳的状况时间是1 ，就是第一个就是待查找的远射，最差的查找状况是O（n），就是最后一个是待查找的元素。
二 折半查找
折半查找是将待查找的数组元素不断的分为两部分，每次淘汰二分之一，但是有个大前提是，元素必须是有序的，如果是无序的则要先进行排序操作，这种查找的方法，类似于找英文字典的Java，我们可以一下子找到字母J开头的，再仔细找。
最佳的状况时间是1，就是第一次分开就查找到了，最差的查找状态是O（n），便是待查找的数据出现在最后一次。
三 费氏查找
费氏查找主要是根据费氏数列1 1 2 3 58 13 ...... 来确定范围，然后再进行查找
四 插补查找
插补查找是一种类似折半查找的查找方法，插补查找是以比例的概念，求出待查找数据的可能位置，然后进行比较，如果该值比待查找的小，表示待查找的值可能出现在该值之前的范围，就这样一直缩小范围来确定最终的目标。
五 二叉查找树
二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。
这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。
折半（二分）查找
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[])
{
intKeyValue = 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(intKeyValue)
{
intLeft; // 左边界变量
intRight; // 右边界变量
intMiddle; // 中位数变量
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
费氏查找
使用费氏数列 1 12 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[])
{
intFinA; // 费氏数
FinA = 1; // 定义费氏数
while (Fib(FinA) <= Max)
FinA++;
intKeyValue = 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)
{
intRoot; // 左边界变量
intDistance_1; // 上一个费氏数
intDistance_2; // 上二个费氏数（差值）
intTemp; // 数据暂存变量
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;
publicstatic 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[])
{
intKeyValue = 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(intKeyValue)
{
intLow; // 插补查找法左边界变量
intHigh; // 插补查找法右边界变量
intMiddle; // 插补查找法中间数
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
二叉查找树算法
形成树型结构，在进行查找
public class BTreeSearch
{
public static int Max = 10;
public static int[] Data = { 15, 2, 13, 6, 17,25, 37, 7, 3, 18 }; // 数据数组
public static int Counter = 1;
public static void main(String args[])
{
inti; // 循环计数变量
BNTreeArrayBNTree = new BNTreeArray(); // 声明二叉树数组
BNTree.TreeData[0] = Data[0];
for(i = 1; i < Max; i++)
BNTree.Create(Data[i]); // 建立二叉查找树
intKeyValue = 25;
// 调用二叉查找法
if(BNTree.BinarySearch(KeyValue) > 0)
//输出查找次数
System.out
.println("SearchTime = " + BNTree.BinarySearch(KeyValue));
else
//输出没有找到数据
System.out.println("No Found!!");
}
}
class BNTreeArray
{
public static int MaxSize = 20;
public static int[] TreeData = newint[MaxSize];
public static int[] RightNode = newint[MaxSize];
public static int[] LeftNode = newint[MaxSize];
public BNTreeArray()
{
inti; // 循环计数变量
for(i = 0; i < MaxSize; i++)
{
TreeData[i] = 0;
RightNode[i] = -1;
LeftNode[i] = -1;
}
}
//----------------------------------------------------
// 建立二叉树
//----------------------------------------------------
public void Create(int Data)
{
inti; // 循环计数变量
intLevel = 0; // 树的阶层数
intPosition = 0;
for(i = 0; TreeData[i] != 0; i++)
;
TreeData[i] = Data;
while (true) // 寻找节点位置
{
//判断是左子树或是右子树
if(Data > TreeData[Level])
{
// 右树是否有下一阶层
if (RightNode[Level] != -1)
Level = RightNode[Level];
else
{
Position = -1; // 设定为右树
break;
}
}
else
{
// 左树是否有下一阶层
if (LeftNode[Level] != -1)
Level = LeftNode[Level];
else
{
Position = 1; // 设定为左树
break;
}
}
}
if(Position == 1) // 建立节点的左右连结
LeftNode[Level] = i; // 连结左子树
else
RightNode[Level] = i; // 连结右子树
}
// ---------------------------------------------------------
// 二叉查找法
//---------------------------------------------------------
public static int BinarySearch(int KeyValue)
{
intPointer; // 现在的节点位置
intCounter; // 查找次数
Pointer = 0;
Counter = 0;
while (Pointer != -1)
{
Counter++;
//找到了欲寻找之节点
if(TreeData[Pointer] == KeyValue)
return Counter; // 传回查找次数
else if (TreeData[Pointer] > KeyValue)
Pointer = LeftNode[Pointer]; // 往左子树找
else
Pointer = RightNode[Pointer];// 往右子树找
}
return 0; // 该节点不在此二叉树中
}
}