二分查找

间复杂度 logN
列表必须有序

public class BinarySearch {

    //二分查找，查找的数组必须有序
    public static int rank(int[] a,int key) {
        int lo = 0;
        int hi = a.length - 1;
        while(lo <= hi){
            int mid = lo + (hi - lo)/2;
            if (a[mid] > key) {
                hi = mid - 1;
            } else if (a[mid] < key ){
                lo = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }


    //二分查找递归写法
    public static int rank2(int[] a,int key){
        return rank2(a,key,0,a.length - 1);
    }

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