折半查找的递归与非递归算法
public class biSearch { /** * @param args * 作者：undoner /* 折半查找--当查找表是有序表时，可采用折半查找; 基本思想：在有序表中，取中间元素作为比较对象，若给定值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<0) low=0; if(high>=r.length) high=r.length-1; //简单的参数验证 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,0,4,5)); System.out.println(bs.BiSearch2(r,0,5,5)); } }