-这是我使用二分搜索算法的 find() 方法:
它就像您期望的那样工作。完全没有问题。
public int find(long searchKey) { int lowerBound = 0; int upperBound = nElems - 1; int currentIndex; while(true) { currentIndex = (lowerBound + upperBound) / 2; if(a[currentIndex] == searchKey) return currentIndex; // found it! else if(lowerBound > upperBound) return nElems; // can't find it else { // so then divide range if(a[currentIndex] < searchKey) lowerBound = currentIndex + 1; // it's in upper half else upperBound = currentIndex - 1; // it's in lower half } // end else divide range } // end while loop } // end find() method
这是使用线性搜索的原始 insert() 方法。很简单,对吧?
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()
我需要修改 insert() 方法以使用 find() 方法的二进制搜索算法。到目前为止,这是我想出的。显然它有问题,但我似乎无法找到问题所在。它根本不起作用,即不执行插入:
public int insertBS(long value) {
int lowerBound = 0;
int upperBound = nElems - 1;
int curIn;
while(true) {
curIn = (lowerBound + upperBound) / 2;
if(a[curIn] == value)
return curIn;
else if(lowerBound > upperBound)
return nElems;
else {
if(a[curIn] < value)
lowerBound = curIn + 1;
else
upperBound = curIn - 1;
}
for(int k=nElems; k>curIn; k--) // move bigger one up
a[k] = a[k-1];
a[curIn] = value;
nElems++;
}
}
语言:Java
使用有序数组。