简单_二分法算法

package sunfa;

//二分法查找
public class TestBinSearch {
	public static void main(String[] args) {
		/**
		 * 集合必须是排序好的，否则查不到。有多个相同的元素则只返回首先被找到的那一个。
		 * 参考:java.util.Arrays.binarySearch方法
		 */
		int[] arr={1,2,3,4,5,611,6,6,7,8,9};
		int r=binSearch(arr, 6);
		System.out.println(r);
	}
	public static int binSearch(int a[],int key){
		int mid = a.length/2;
		if(key==mid){
			return mid;
		}
		
		int start=0;
		int end=a.length-1;
		while(start<=end){
			mid = (end-start)/2+start;//避免(start+end)/2超过 int范围
			if(key<a[mid]){
				end = mid-1;
			}else if(key>a[mid]){
				start=mid+1;
			}else{
				return mid;
			}
		}
		return -1;
	}
}