问题描述
我正在修改一些代码,但我意识到了一些我从来不知道的事情.正常的二分搜索将在数据集中为多次出现的键返回随机索引.如何修改下面的代码以返回第一次出现?这是人们做的事情吗?
I'm tinkering with some code and I realized something I never knew. A normal binary search will return a random index in a data set for a key that occurs more than once. How can I modify this code below to return the first occurrence? Is this something people do?
//ripped from the JDK
public static int binarySearchValue(InvertedContainer.InvertedIndex[] a, long key) {
return bSearchVal(a, 0, a.length, key);
}
private static int bSearchVal(InvertedContainer.InvertedIndex[] a, int fromIndex,
int toIndex, long key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
long midVal = a[mid].val;
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return (low); // key not found. return insertion point
}
推荐答案
找到一个匹配的值,你基本上需要遍历集合,直到找到一个没有的条目 匹配.
Having found a matching value, you basically need to walk up the collection until you find an entry which doesn't match.
您可以潜在地通过立即获取低于您要查找的键的索引来使其更快,然后在两者之间进行二进制切割 - 但我可能会选择更简单的版本,除非您有大量相等的条目,否则它可能足够高效".
You could potentially make it faster by fetching the index of a key immediately lower than the one you were looking for, then do a binary chop between the two - but I'd probably go for the simpler version, which is likely to be "efficient enough" unless you've got a really large number of equal entries.
这篇关于二分查找中的第一次出现的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!