package Ceshi;
public class biSearch {
/**
* @param args
*/
/*
折半查找--当查找表是有序表时，可采用折半查找;
基本思想：在有序表中，取中间元素作为比较对象，若给定值K与中间记录关键字相等，则查找成功；
若给定值K小于中间记录的关键字，则在表的左半区继续查找；
若给定值K大于中间记录的关键字，则在表的右半区继续查找，不断重复，直到查找成功/失败。
*/
//折半查找非递归算法
//查询成功返回该对象的下标序号，失败时返回-1。
int BiSearch(int r[],int n,int k)
{
int low=0;
int high=n-1;
while(low<=high)
{
int mid=(low+high)/2;
if(r[mid]==k)
return mid;
else
if(r[mid]<k)
low=mid+1;
else
high=mid-1;
}
return -1;
}
//折半查找递归算法
//查询成功返回该对象的下标序号，失败时返回-1。
int BiSearch2(int r[],int low,int high,int k)
{
if(low>high)
return -1;
else
{
int mid=(low+high)/2;
if(r[mid]==k)
return mid;
else
if(r[mid]<k)
return BiSearch2(r,mid+1,high,k);
else
return BiSearch2(r,low,mid-1,k);
}
}
public static void main
(String[] args
) { biSearch bs=new biSearch();
int r[]={1,2,3,4,5};
System.
out.
println(bs.
BiSearch(r,
5,
5)); System.
out.
println(bs.
BiSearch2(r,
1,
5,
5)); }
}
//java/5829