当前位置 博文首页 > aaa_hao的博客：Java语言实现线性查找和二分法查找
在一列给定的值中进行搜索，从一端开始逐一检查每个元素，直到找到所需元素的过程。
如果查找池是某种类型的一个表，比如一个数组，简单的查找方法是从表头开始，一次将每一个值与目标元素进行比较。最后，或者查找到目标，或者达到表尾，而目标不存在于组中，这个方法称为线性查找。
public class SearchAlgorithm {
public static void main(String[] args) {
//查找(或搜索)
//线性查找
String[] arr = new String[]{"AA","BB","CC","DD","EE","FF"};
String dest = "EE"; //目标元素
boolean isFlag = true; //定义一个标记变量，用来记录程序是否找到了指定元素
for (int i = 0;i < arr.length;i++){
if(dest.equals(arr[i])){ //调用String类中的equals方法来判断两个字符串相等
System.out.println("找到了指定的元素，位置为：" + i);
isFlag = false; //若程序找到了指定元素，则将isFlag置为false，否则isFlag仍为true
break; //倘若找到指定元素，直接跳出查找元素的循环
}
}
//若程序未曾找到指定元素，即无法进入上述循环中的if语句块，isFlag仍然是true，得以执行下面这段if语句块
if(isFlag){
System.out.println("很遗憾，没有找到指定元素哦！");
}
}
}
二分查找又称折半查找，它是一种效率较高的查找方法。
1.必须采用顺序存储结构 。
2.必须按关键字大小有序排列。
二分法查找的优点是元素比较次数少、查找速度快、平均性能好;
其缺点是要求待查表为有序表，且插入删除困难。因此，这种查找方法适用于不经常变动而查找频繁的有序列表。
首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
假设待查数组长度(问题规模)为n，则其算法复杂度为o(log(n))
public class ArrayTest3 {
public static void main(String[] args) {
//二分法查找
//前提：所要查找的数组必须有序
int[] arr = new int[]{-98,-34,2,34,54,66,79,105,210,333};
int dest = 34; //目标元素
int head = 0; //初始的首索引
int end = arr.length - 1; //初始的末索引
boolean isFlag = true;
while(head <= end){
int middle = (head + end)/2; //折中得到中间元素
if (dest == arr[middle]){ //若中间元素刚好与目标元素相等，则直接查找成功
System.out.println("找到了指定的元素，位置为：" + middle);
isFlag = false;
break;
}else if (arr[middle] > dest){ //若中间元素比目标元素大，则查找前半子表
end = middle -1; //将前半子表的最后一个元素赋给end，得到一个新的末索引
}else { //arr[middle] < dest ,中间元素比目标元素小，则查找后半子表
head = middle + 1; //将后半子表的第一个元素赋给head，得到一个新的首索引
}
/*
经历一次循环后无法找到指定元素就会进入新一次循环，新一次循环的待查表为上一次循环的前半子表或后半子表
*/
}
//若程序未曾找到指定元素，即无法进入上述循环中的if语句块，isFlag仍然是true，得以执行下面这段if语句块
if (isFlag){
System.out.println("很遗憾，没有找到指定元素哦！");
}
}
}
