二分查找法 (Binary Search)

对于有序数列，才能使用二分查找法

有递归实现和非递归实现两种

非递归实现

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/2 + r/2;
        if (arr[mid].compareTo(target) == 0) {
            return mid;
        } else if (arr[mid].compareTo(target) > 0) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return -1;
}

递归实现

public static int find(Comparable[] arr, Comparable target) {
    return _find(arr, 0, arr.length - 1, target);
}

private static int _find(Comparable[] arr, int l, int r, Comparable target) {
    if (l > r) {
        return -1;
    }
    int mid = l/2 + r/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);
    }
}