首页 >  JAVA频道 > 名师答疑 > 

java折半查找法

java折半查找法

作者:yjl 来源:华育国际 时间:2015-02-27 访问次数:1333
折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4,要查找的数是X,其基本思想是: 设查找数据的范围下限为l=1,

折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4,要查找的数是X,其基本思想是: 设查找数据的范围下限为l=1,上限为h=5,求中点m=(l+h)/2,用X与中点元素am比较,若X等于am,即找到,停止查找;否则,若X大于am,替换下限l=m+1,到下半段继续查找;若X小于am,换上限h=m-1,到上半段继续查找;如此重复前面的过程直到找到或者l>h为止。如果l>h,说明没有此数,打印找不到信息,程序结束。
 
 
方法一:
package suanfa;
import java.util.*;
public class zheban {
public static void main(String[]args)
{
int[]a={1,3,6,8,9,89,765};
int time=search(a,8);
System.out.println(time);
}
public static int search(int[]a,int key)
{
int low=1;
int high=a.length;
int mid;
while(low<high)
{
mid=(low+high)/2;
if(key==a[mid-1])
return mid-1;
else if(key>a[mid-1])
low=mid+1;
else
high=mid-1;
}
return 0;
}
}
 
 
方法二:
package m;
import java.util.*;
public class zheban {
public static int[]data={1,3,5,7,9,11,22,44,67,89};
public static void main(String[]args)
{
System.out.println("please enter the data you will find:");
Scanner scan=new Scanner(System.in);
int key=scan.nextInt();
zheban(key,0,9);
}
public static boolean zheban(int key,int low,int high)
{
int l=low;
int h=high;
int mid;
while(l<h)
{
mid=(l+h)/2;
if(data[mid]==key)
{
System.out.println("find "+"the data is in array "+(mid+1));
return true;
}
else if(key<data[mid])
h=mid-1;
else if(key>data[mid])
l=mid+1;
}
System.out.println("failed");
return false;
}
}