二分查找

电话面试

package 二分查找;
public class BinarySearch {
    public static int binarySearch(int key, int[] data){
        return binarySearch2(key, data, 0, data.length-1);
    }
    public static int binarySearch(int key, int[] data, int low, int height){
        if(low > height)
            return -1;
        int mid = (low + height) >>> 1;
        if(key > data[mid])
            return binarySearch(key, data, mid+1, height);
        else if(key < data[mid])
            return binarySearch(key, data, low, mid-1);
        else
            return mid;
    }
    public static int binarySearch2(int key, int[] data, int low, int height){
        while(low <= height){
            int mid = (low + height) >>> 1;
            if(key > data[mid])
                low = mid + 1;
            else if(key < data[mid])
                height = mid - 1;
            else
                return mid;
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] data = {1,2,3,4,5,6,7,8,20};
        System.out.println(binarySearch(20, data));
    }
}