的范围内

Question

数二分查找范围这是我的代码：

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]]; 

所以我想要做的是这样的：我有一个排序的字典，权力键，和一个正常的迭代的值。我必须打印在指定范围内有多少个键。字典中的一些条目：[1,1]，[4,2]，[8,3]，[9,4]，[16,5]，[25,6]，[ 27,7]，[32,8] 限制：2和10 2 - 10中的数字：4，8，9 = 3个数字。

随着BinarySearch我试图快速找到我想要的数字，然后减去Potencias [onlyP [superiorindex]] - Potencias [onlyP [inferiorindex]]找到有多少数字在该范围内。不幸的是，它不适用于所有情况，它有时会给出比实际数量少的数字。这怎么解决？提前致谢。如果我选择极限：4和4 ...它返回0，但答案是1. 限制：1和10^9（整个范围）返回32669 .. 。但答案是32670. 该算法忽略权力。

Answer 1

最后，阅读了文档。注意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; 

说明：

对于较低指数，我们只取补，因为二分查找返回的第一个项目> =下界的索引。

对于上面的索引，我们还补充了一个补码，因为我们想要第一个项目< = upperBound（not> = upperBound这是BinarySearch的返回值）。

Answer 2

看来，你没有做它的赖特韦进行后处理的二进制搜索返回值： http://msdn.microsoft.com/en-us/library/5kwds4b1.aspx

应该是： if (inferiorindex < 0) inferiorindex = ~inferiorindex;

（未经测试）

此外，名单支持二进制搜索，所以你不必做Array.BinarySearch的事情，只需在onlyP上工作。

Answer 3

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;