如何将线性搜索转换为二分搜索?
- 这是我使用二分搜索算法的 find() 方法:
它的工作原理正如您所期望的那样。完全没有问题。
public int find(long searchKey) { int 下界 = 0; int upperBound = nElems - 1; int 当前索引; 而(真){ 当前索引 = (下界 + 上界) / 2; if(a[当前索引] == 搜索关键字) 返回当前索引; // 找到了! else if(下界>上界) 返回 nElem; // 找不到它 else { // 所以然后划分范围 if(a[当前索引] < 搜索关键字) 下界 = 当前索引 + 1; // 它在上半部分 别的 upperBound = 当前索引 - 1; // 它在下半部分 } // 结束 else 划分范围 } // 结束 while 循环 } // 结束 find() 方法
这是使用线性搜索的原始 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
使用有序数组。
- This is my find() method using Binary Search algorithm:
It works just as you would expect it to. No problems at all.
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
Here's the original insert() method using linear search. Pretty straightforward, right?
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()
I need to modify the insert() method to use the binary search algorithm of the find() method. Here's what I came up with so far. Obviously there's something wrong with it, but I can't seem to find the problem. It doesn't work at all, i.e. no insertions are performed:
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++;
}
}
Language: Java
Using ordered array.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(4)
好吧,很明显为什么没有插入该值,因为您从未插入该值。一旦找到要插入的位置的索引,您只需从函数返回而不执行任何操作。
well, it's obvious why the value isn't inserted, it's because you never inserted the value. Once you found the index of the position to insert you simply return from the function without doing anything.
嗯,为什么不直接调用你的查找函数呢?
这样,当您优化/更改查找功能时,您的插入功能也会更快!
作为旁注,我认为您的 find 函数不会给您所写的预期行为。如果你有一个 [0,1,4,5,9] 列表并且我搜索 7,我将得到 nElems (5) 的索引,这可能会被误解,因为索引 0 到 4 处的值都小于7. 看起来有点奇怪。
Um, why not just CALL your find function?
This way, when you optimize/change your find function, your insert function will go faster, too!
As a side note, I think your find function will not give you expected behavior, as written. If you have a list of [0,1,4,5,9] and I search for 7, I will get an index of nElems (5), which could be misinterpreted as the values at indexes 0 to 4 are all less than 7. Seems a little wonky.
在移动元素之前,您需要执行二分搜索来找到插入索引。在最后一个代码片段中,您尝试在二分搜索完成之前使用变量
curIn
在while
循环内移动元素。尝试将for
循环移到while
循环之外。You need to perform the binary search to find the insertion index before moving elements. In your last code snippet, you are attempting to use the variable
curIn
to move elements inside yourwhile
loop before your binary search has finished. Try moving thefor
loop outside of thewhile
loop.