java - 二进制搜索，返回应该插入值的索引

Question

除了普通函数之外，我还需要进行二进制搜索，当找不到该值时，它会返回我必须在其中插入新元素进行排序的索引。在下面的代码中，第二个 for 用于搜索要交换元素的索引。我需要做一个用二进制搜索替换它的函数。这种方法会是什么样子？

void insertion (int n, int v[])
{
   for (int j = 1; j < n; ++j) {
   int x = v[j];
   int i;
// this for searches where the value should be inserted
   for (i = j-1; i >= 0 && v[i] > x; --i) 
        v[i+1] = v[i];
        v[i+1] = x;
   }
}

我知道正常的二进制搜索是这样的。我需要改变什么？

    static int BinarySearchR (int [] array, int l, int r, int key) {
        int mid = ((r - l) / 2) + l;
        if (array[mid] == key) return mid;
        else if (array[mid] > key) return BinarySearchR(array, l, mid- 1, key);
        else if(array[mid] < key) return BinarySearchR(array, mid + 1, r, key); 
        return -1;
    }

标签： javabinary-search

Answer 1

经过一些调整，它起作用了：

public static int BuscaBinariaI(int [] arr, int l, int r, int n) {
        int mid = 0;
            while(l < r){
                mid = l + (r - l)/2;
                if(arr[mid] == n) {
                    return -1;
                } 
                else if(arr[mid] > n){
                    r = mid - 1;
                    BuscaBinariaI( arr, l, r, n);
                }
                else {
                    l = mid + 1;
                    BuscaBinariaI( arr, l, r, n);
                }
            }
            if (mid>=arr.length) return arr.length;
            else if(arr[mid] > n) return mid ;
            else return mid + 1;
    }