java - 使用二分查找递归返回元素在排序数组中的插入位置

Question

如果该元素存在，我想从排序数组中返回该元素的位置，否则我想返回应插入该元素的插入位置。这是我的代码:

    public static int bs(int[] array, int left, int right, int elem) {
    if (left > right) {
        return left;
    } else {
        int middle;
        middle = (left + right) / 2;
        if (left == right) { // used to return the insert position
            return left;
        } else if (elem > array[middle]) {
            return bs(array, middle + 1, right, elem);
        } else if ((elem < array[middle])) {
            return bs(array, left, middle - 1, elem);
        } else {
            return middle; // element existed into array
        }
    }
}

例如:

array = [ 2 5 8 10], elem = 8 => 将返回 2

array = [ 2 5 8 10], elem = 6 => 将返回 1

array = [ 2 7 14 22 32 56 88 91 102], elem = 3 => 将返回 1(但上面的程序返回 0)

Answer 1

您的错误是在 bs(left,middle-1) 时从 split 中删除 array[middle]。相反，您需要使用 bs(left,middle) 和 bs(middle+1,right)。我将 print 添加到递归调用中并轻松找到了它。

public static int bs(int[] array, int left, int right, int elem) {
    System.out.println("["+left+", "+right+"]");
    if (left > right) {
        return left;
    } else {
        int middle;
        middle = (left + right) / 2;
        if (left == right) { // used to return the insert position
            return left;
        } else if (elem > array[middle]) {
            return bs(array, middle + 1, right, elem);
        } else if ((elem < array[middle])) {
            return bs(array, left, middle, elem); //<-- was: middle-1
        } else {
            return middle; // element existed into array
        }
    }
}

而且我认为这种风格会更好;)

public static int bs2(int[] array, int left, int right, int elem) {
    System.out.println("["+left+", "+right+"]");
    if (left >= right)
        return left;

    int middle;
    middle = (left + right) / 2;
    if (elem > array[middle])
        return bs(array, middle + 1, right, elem);
    if ((elem < array[middle]))
        return bs(array, left, middle, elem); //<--- was: middle-1
    return middle; // element existed into array
}