二进制搜索中的第一个匹配项
二进制搜索中的第一个匹配项
提问于 2011-07-13 16:47:47
我正在修改一些代码，我意识到了一些我从来不知道的事情。正常的二进制搜索将在数据集中返回一个多次出现的键的随机索引。如何修改下面的代码以返回第一个匹配项？这是人们做的事情吗？
//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
}回答 11
Stack Overflow用户
回答已采纳
发布于 2011-07-13 16:49:58
找到匹配值后，基本上需要遍历集合，直到找到一个不匹配的条目。
你可以通过直接获取比你所寻找的键更低的键的索引来使它更快，然后在这两个键之间进行二进制切分-但我可能会选择更简单的版本，它很可能是“足够有效”的，除非你有非常多的相等条目。
Stack Overflow用户
发布于 2011-07-13 17:07:19
对Jon Skeets帖子的补充：
潜在的更快的实现实际上并不难实现，并且只添加了2行代码，下面是我如何做到的：
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else if (low != mid) //Equal but range is not fully scanned
high = mid; //Set upper bound to current number and rescan
else //Equal and full range is scanned
return mid;Stack Overflow用户
发布于 2011-07-13 17:03:22
你可以实现“下限”算法，而不是二进制搜索。例如，在C++/STL中使用了这种算法，并且它转换成Java的文本是直接的。下界的算法复杂度也是O(log )，与二进制搜索算法相同。这比首先使用二进制搜索和线性搜索第一个匹配元素要好-这将具有最坏的情况行为O(n)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/6676360
复制相关文章
相似问题