java如何将线性搜索转换为二进制搜索?
-这是我使用二进制搜索算法的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
使用有序数组
# 1 楼答案
# 2 楼答案
为什么不直接调用find函数呢
这样,当您优化/更改find函数时,插入函数也会更快
作为补充说明,我认为find函数不会给出预期的行为。如果你有一个[0,1,4,5,9]的列表,我搜索7,我会得到nElems(5)的索引,这可能会被误解为索引0到4的值都小于7。看起来有点不稳定
# 3 楼答案
很明显为什么没有插入值,因为你从来没有插入过值。找到要插入的位置的索引后,只需从函数返回,无需执行任何操作
# 4 楼答案
在移动元素之前,需要执行二进制搜索以查找插入索引。在上一个代码段中,您试图在二进制搜索完成之前使用变量
curIn
移动while
循环中的元素。尝试将for
循环移到while
循环之外