java如何使用二进制搜索找到将值插入有序数组的位置?
我正在做有关数据结构和算法的书中的编程项目,我需要使用二进制搜索实现有序数组的插入
我使用线性方法的初始实现是:
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()
我认为我的主要错误如下:
- 我没有任何处理空数组大小写的逻辑李>
请给我一些建议。我大约一周前才开始学习这些东西,所以一些解释会很好
提前谢谢你,尼克
# 1 楼答案
在循环过程中,可以保持循环不变(插入位置始终在间隔
[lowerBound upperBound]
)所以当
arr[curIn] > value
时,将间隔减半为[lowerBound curIn]
当
arr[curIn] <= value
时,将间隔减半至[curIn+1 upperBound]
在循环之后,lowerBound是要插入的位置