二分查找

二分查找的时间复杂度logn，前题是有序

先与l+(r-l)/2处比较就是中间位置比较，为什么不是（l+r）/2呢，因为l+r相加有可能会发生溢出。

小于中间位置，则在左边位置继续重复上一步，大于则在右边重复，如此重复即可。

public static int find(Comparable[] arr, Comparable target) {

// 在arr[l...r]之中查找target

    int l =0, r = arr.length-1;

    while( l <= r ){

//int mid = (l + r)/2;

        // 防止极端情况下的整形溢出，使用下面的逻辑求出mid

        int mid = l + (r-l)/2;

        if( arr[mid].compareTo(target) ==0 )

return mid;

        if( arr[mid].compareTo(target) >0 )

r = mid -1;

else

            l = mid +1;

    }

return -1;

}

递归实现

private static int find(Comparable[] arr, int l, int r, Comparable target){

if( l > r )

return -1;

    //int mid = (l+r)/2;

    // 防止极端情况下的整形溢出，使用下面的逻辑求出mid

    int mid = l + (r-l)/2;

    if( arr[mid].compareTo(target) ==0 )

return mid;

    else if( arr[mid].compareTo(target) >0 )

return find(arr, l, mid-1, target);

else

        return find(arr, mid+1, r, target);

}