Java线性查找和二分查找。
一 线性查找
定义：在一列给定的值中进行搜索，从一端开始逐一检查每个元素，直到找到所需元素的过程。
线性查找又称为顺序查找。如果查找池是某种类型的一个表，比如一个数组，简单的查找方法是从表头开始，一次将每一个值与目标元素进行比较。最后，或者查找到目标，或者达到表尾，而目标不存在于组中，这个方法称为线性查找。
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
二 折半查找
定义：二分查找又称折半查找，它是一种效率较高的查找方法。
【二分查找要求】：1.必须采用顺序存储结构 2.必须按关键字大小有序排列。
【优缺点】折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
【算法思想】首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
【算法复杂度】假设其数组长度为n，其算法复杂度为o（log（n））
下面提供一段二分查找实现的伪代码:
BinarySearch(max,min,des)
mid-<(max+min)/2
while(min<=max)
mid=(min+max)/2
if mid=des then
return mid
elseif mid >des then
max=mid-1
else
min=mid+1
return max
折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如 果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右 半部继续搜索x。
Java的二分查找算法
public class BinarySearch {
/**
* 二分查找算法
*
* @param srcArray 有序数组
* @param des 查找元素
* @return des的数组下标，没找到返回-1
*/
public static int binarySearch(int[] srcArray, int des)
{
int low = 0;
int high = srcArray.length-1;
while(low <= high) {
int middle = (low + high)/2;
if(des == srcArray[middle]) {
return middle;
}else if(des <srcArray[middle]) {
high = middle – 1;
}else {
low = middle + 1;
}
}
return -1;
}
public static void main(String[] args)
{
int[] src = new int[] {1, 3, 5, 7, 8, 9};
System.out.println(binarySearch(src, 3));
}
}
Java代码
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