java如何使用二进制搜索找到将值插入有序数组的位置？

Question

我正在做有关数据结构和算法的书中的编程项目，我需要使用二进制搜索实现有序数组的插入

我使用线性方法的初始实现是：

public void insert(long value) {      // put element into array
    int j;
    for (j = 0; j < nElems; j++)      // find where it goes
        if (a[j] > value)             // (linear search)
            break;
    for (int k = nElems; k > j; k--)  // move bigger ones up
        a[k] = a[k-1];
    a[j] = value;                     // insert it
    nElems++;                         // increment size
}  // end insert()

但是，当我尝试使用二进制搜索方法创建类似的东西时，我被卡住了。 以下是我所做的：

public void insert(long value) {
    int lowerBound = 0;
    int upperBound = nElems-1;
    int curIn;

    while(lowerBound < upperBound) {

        curIn = (lowerBound + upperBound) / 2;

        if(arr[curIn]>value && arr[curIn-1] < value) {
            for(int k=nElems; k>curIn; k--) 
                arr[k] = arr[k-1];
            arr[curIn] = value;
        } else {
            if(arr[curIn] > value)
                upperBound = curIn-1;
            else
                lowerBound = curIn+1;
        }
    }   
}  // end insert()

我认为我的主要错误如下：

• 我没有任何处理空数组大小写的逻辑

请给我一些建议。我大约一周前才开始学习这些东西，所以一些解释会很好

提前谢谢你，尼克

Answer 1

在循环过程中，可以保持循环不变（插入位置始终在间隔[lowerBound upperBound]）

所以当arr[curIn] > value时，将间隔减半为[lowerBound curIn]

当arr[curIn] <= value时，将间隔减半至[curIn+1 upperBound]

在循环之后，lowerBound是要插入的位置

//Assume arr, nElems are declared somewhere else and enough space to insert...
public void insert(long value) {
    int lowerBound = 0;
    int upperBound = nElems;
    int curIn;
    while(lowerBound < upperBound) {
        curIn = (lowerBound+upperBpund)/2;
        if(arr[curIn] > value) {
            upperBound = curIn;
        } else {
            lowerBound = curIn+1;
        }
    }
    //note lowerBound may equal nElems, it works anyway
    for(int k = nElems; k > lowerBound; k ) {
        arr[k] = arr[k-1];
    }
    arr[lowerBound] = value;
    nElems++;
}