Return 使用二进制搜索递归将元素插入排序数组的位置

Question

我想 return 排序数组中某个元素的位置（如果该元素存在）否则我想 return 应该插入该元素的插入位置。这是我的代码：

    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 => 将 return 2

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

array = [ 2 7 14 22 32 56 88 91 102], elem = 3 => 会return1（但是上面的程序returns 0）

Answer 1

希望我没听错。这是我的第一个 post 所以请怜悯我:)。

一开始我觉得 array = [ 2 5 8 10], elem = 6 => will return 2 是正确的，因为 6 > 5 所以它的索引为 2。或者你想用 6 替换 5 ？如果你想替换去掉我评论的“//”。

public static int getPosition(int[] arr, int value)
{
    int position = 0;

    for (int i = 0; i < arr.length; i++)
    {
        if (arr[i] == value)
        {
            position = i;
            break;
        } else
            position = -1;
    }

    if (position == -1)
    {
        int[] arr2 = new int[arr.length + 1];
        System.arraycopy(arr, 0, arr2, 0, arr.length);
        arr2[arr.length] = value;

        Arrays.sort(arr2);
        position = getPosition(arr2, value);//-1;
    }
    return position;
}

public static void main(String[] args)
{

    int[] arr = { 2, 5, 8, 10 };

    System.out.println(getPosition(arr, 6));

}

Answer 2

你的错误是在 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
}

Return 使用二进制搜索递归将元素插入排序数组的位置

Return the insert position of an element into a sorted array with Binary Search Recursion

java

binary-search