BinarySearch限制范围内的数字

本文关键字：数字 范围内 BinarySearch | 更新日期: 2023-09-27 18:20:35

这是我的代码：

SortedDictionary<int,int> Numbers = new SortedDictionary<int,int>();
List<int> onlyP = new List<int>(Numbers.Keys);
int Inferior = int.Parse(toks[0]);
int Superior = int.Parse(toks[1]);
int count = 0;
int inferiorindex = Array.BinarySearch(Numbers.Keys.ToArray(), Inferior);
if (inferiorindex < 0) inferiorindex = (inferiorindex * -1) - 1;
int superiorindex = Array.BinarySearch(Numbers.Keys.ToArray(), Superior);
if (superiorindex < 0) superiorindex = (superiorindex * -1) - 1;
count = Numbers[onlyP[superiorindex]] - Numbers[onlyP[inferiorindex]];

所以我想做的是：我有一个排序字典，以幂为键，以正常迭代为值。我必须打印出在指定范围内可以容纳多少个键。

示例：dict的一些条目：[1，1]，[4，2]，[8，3]，[9，4]，[16，5]，[25，6]，[27，7]，[32，8]限值：2和102-10:4,8,9=3个数字。

使用BinarySearch，我试图快速找到我想要的数字，然后减去Potencias[onlyP[superiorindex]]-Potencias[onlyP[inderiorindex]]，找出范围内有多少数字。不幸的是，它并不是适用于所有的情况，而且它有时给出的数字比实际数量少。如何解决这个问题？提前谢谢。

[EDIT]问题示例：如果我选择限制：4和4…则返回0，但答案为1。限制：1和10^9（整个范围）返回32669…但答案是32670。算法忽略了幂。

BinarySearch限制范围内的数字

最后，阅读了文档。请注意，upperIndex转换中的-1和返回值中的+1，这些都很重要。

var numbers = new[] { 1, 4, 8, 9, 16, 25, 27, 32 };
var lowerBound = 4;
var upperBound = 17;
int lowerIndex = Array.BinarySearch(numbers, lowerBound);
if (lowerIndex < 0) lowerIndex = ~lowerIndex;
// - 1 here because we want the index of the item that is <= upper bound.
int upperIndex = Array.BinarySearch(numbers, upperBound);
if (upperIndex < 0) upperIndex = ~upperIndex - 1;
return (upperIndex - lowerIndex) + 1;

解释：

对于较低的索引，我们只使用补码，因为BinarySearch返回第一项>=lowerBound的索引。

对于上索引，我们额外地从补码中减去一，因为我们想要第一项<=upperBound（而不是>=upperBoundBinarySearch返回的值）。

似乎没有以正确的方式对二进制搜索返回值进行后期处理：http://msdn.microsoft.com/en-us/library/5kwds4b1.aspx

应为：if (inferiorindex < 0) inferiorindex = ~inferiorindex;

（未经测试）

此外，List支持二进制搜索，所以您不必做Array.BinarySearch的事情，只需处理onlyP即可。

int inferiorindex = Array.BinarySearch<int>(keys, Inferior);
if (inferiorindex < 0) {
    inferiorindex = ~inferiorindex;
}
int superiorindex = Array.BinarySearch<int>(keys, Superior);
if (superiorindex < 0) {
    // superiorindex is the binary complement of the next higher.
    // -1 because we want the highest.
    superiorindex = ~superiorindex - 1;
}
int count = superiorindex - inferiorindex + 1;
相关文章：