二分查找

前言

查找操作，通俗的讲，就是给定一个值key，在一个数据结构中找出关键字为key的元素。而基于线性表的查找算法有顺序查找（O（n）），二分查找和分块查找

二分查找

主要用于已排序的顺序表
算法描述：假定顺序表已按照升序排列，从表的中间位置开始比较，如果当前元素的关键字等于给定值，则查找成功，否则，若给定的值小于当前元素关键字，则在表的前半段继续查找，反之，在后半段查找，以此重复，直到获得查找结果

public class BSArray {

	//在升序排列的数组中，若找到关键字，则返回相应下标，否则返回-1
	public static<T> int binarySearch(Comparable<T>[] value,T key){
		return binarySearch(value,0,value.length-1,key);
	}
	
	public static<T> int binarySearch(Comparable<T>[] value,int begin,int end,T key){
		if(key!=null)
			while(begin<=end){    //边界有效
				int mid=(begin+end)/2;  //中间位置，当前比较元素位置
		System.out.println(value[mid]+"?");
		if(value[mid].compareTo(key)==0) //对象比较大小
			return mid;                  //查找成功
		if(value[mid].compareTo(key)>0)  
			end=mid-1;                    //缩小到前半段
		else
			begin=mid+1;                 //缩小到后半段
	} 
	return -1;                           //查找不成功
	}
}