java 实现二分查询

1. 非递归写法：
public class BinarySearch {

	/**
	 * 二分查找
	 * 思路：对于有序的一组数据，
	 * 从中间找起，如果找到则返回；如果没有，且值比中间小，则其左边再从相对应的中间找起，右边同理。
	 */
	public static void main(String[] args) {
		int[] arr = {1,3,4,7,8,9,20,33,48};
		System.out.println(search(arr, 20));
		
		int[] i = {1,2,3,4,5,6,7,8};
		System.out.println(search(i, 5));
	}
	
	public static int search(int[] arr, int key) {
		if(arr.length > 0) {//如果数组里有元素存在，则执行
			
			//初始高低位
			int low = 0;
			int high = arr.length-1;
			
			while(low <= high) {
				int mid = (low + high)/2;	//中间量定位
			
				if(key == arr[mid]) {	//找到就返回
					return mid;
				} 
				else if(key > arr[mid]){	//值比中间的大从右边找
					low = mid +1;
				}
				else {	//值比中间的小，从左边找
					high = mid - 1;
				}
			}
		}
		return -1;	//没找到返回-1
	}

}

 

 

 

2. 递归算法：

public static int sort(int []array,int a,int lo,int hi){
        if(lo<=hi){
            int mid=(lo+hi)/2;
            if(a==array[mid]){
                return mid+1;
            }
            else if(a>array[mid]){
                return sort(array,a,mid+1,hi);
            }else{
                return sort(array,a,lo,mid-1);
            }
        }
        return -1;
    }