话说“查找”
在日常生活中,人们几乎每天都要进行"查找".例如,在电话号码薄中查找某单位或某人的电话号码,在字典中查阅某个词的读音和含义等.查找的关键问题是如何快速地到待查的内容,例如,查字典的关键是如何快速地确定待查之字在字典的哪一页.对于浩如烟海的计算机中的数据,有相当多的数据时以数组的形式组织与存放的,以数组的形式组织和存放数据的数据结构被称为顺序表.对于顺序表的查找,人们已经发明了许多种算法,典型的有顺序查找和二分(折半、对半）查找。
顺序查找是让关键字与队列中的数从第一个开始逐个比较，直到找出与给定关键字相同的数为止。 这种查找的效率相对较低。
我们来看一个例子，
import java.util.Scanner;
public class Search{
public static int[] Data =
{
1,7,9,12,15,
16,20,32,35,57,
78,80,83,89,90,
92,97,108,120,177
};
public static int Counter = 1;
public static void main(String args[]){
int n;
System.out.println("Please enter your key value:");
Scanner console = new Scanner(System.in);
int KeyValue = console.nextInt();
if(Seq_Search((int)KeyValue)){
//输出查找次数
System.out.println("");
System.out.println("Search Time = " + (int)Counter);
n=(int) Counter-1;
System.out.println("所查整数在数组中的位置下标是：" + n);
}
else{
//输出没有找到的数据
System.out.println("");
System.out.println("NO Found!!!");
}
}
//顺序查找
public static boolean Seq_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
}
}
输出的结果：
在这个例子中，我们看到查找120这个元素，需要查找19次，特别的麻烦。那么我们来看看二分查找吧。
二分查找是在一个有序表（数组）是由其值由小到大或由大到小依次存放的，这里我们以值由小到大排序为例）中，每次都将待查值与中间的那个元素比较，若相等则查找成功，否则，调整查找范围，若中间那个元素的值小于待查值，则在表的后一半中查找，若中间那个元素的值大于待查值，则在表的前一半中查找；如此循环，每次只与一半中的一个元素比较，可使查找效率大大提高。
我们以一个例子来看看：
//设数组中的数值是由小到大存放的，编写二分查找程序
import java.io.*;
class FindSearch
{
int binarySearch(int arr[],int searchValue)
{
int low=0; //low是第一个数组元素的小标
int high=arr.length-1;
int mid=(low+high)/2;
while(low<=high && arr[mid]!=searchValue)
{
if (arr[mid]<searchValue)
low=mid+1; //要找的数可能在数组的后一半部分中
else
high=mid-1;//要找的数可能在数组的前半部分中
mid=(low+high)/2;
}
if (low>high)mid=-1;
return mid; //mid是数组元素下标，若为-1，则表示不存在要查的元素
}
}
public class seek
{
public static void main(String[] args)throws IOException
{
BufferedReader keyin=new BufferedReader(new InputStreamReader(System.in));
int i,k,search,mid;
String c1;
int arr[]={2,4,7,18,25,34,56,68,89};
System.out.println("打印原始数据");
for(i=0;i<arr.length;i++)
System.out.print(" "+arr[i]);
System.out.println("\n");
System.out.println("请输入要查找的整数");
c1=keyin.readLine();
search=Integer.parseInt(c1); //取出字符串转换为整型数赋给search
FindSearch p1=new FindSearch();
mid=p1.binarySearch(arr,search);
if(mid==-1)
System.out.println("没找到！");
else
System.out.println("所查整数在数组中的位置下标是:"+mid);
}
}
输出的结果为：
我们以查找68为例的二分查找的比较和下标调整过程：
- 1楼lfmilaoshi昨天 22:58
- 算法。。。基础积累。。。。米老师