我的书C# 3.0 Cookbook by O'Reilly有以下让我感到困惑的例子。 (下面是准确的转录。)
// Count the number of times an item appears in the sort List<T>.
public static int BinarySearchCountAll<T>(this List<T> myList, T searchValue)
{
// Search for the first item.
int center = myList.BinarySearch(searchValue);
int left = center;
while (left < 0 && myList[left-1].Equals(searchValue))
{
left -= 1;
}
int right = center;
while (right < (myList.Count - 1) && myList[right+1].Equals(searchValue))
{
right += 1;
}
return (right - left) + 1;
}
特别是,我从
开始感到困惑int center = myList.BinarySearch(searchValue);
int left = center;
while (left < 0 && myList[left-1].Equals(searchValue))
片段。根据the documentation on the BinarySearch方法,left
是元素的索引。那么条件如何
left < 0 && myList[left-1].Equals(searchValue)
在while
循环有意义吗?因为短路,如果left < 0
然后右边myList[left-1].Equals(searchValue)
被评估但是myList[left-1]
正在访问负索引!对吧?
我确实阅读了有关如果未找到元素在 BinarySearch 中会发生什么的部分
a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count.
而且我无法弄清楚我书中的这种方法是否试图利用这一事实。似乎是一种非常令人困惑的编写应该是简单方法的方式,否则我没有正确理解它。因为如果我理解正确 BinarySearch
返回找到的任意第一个匹配元素然后我不明白为什么该方法不能只是
// Count the number of times an item appears in the sort List<T>.
public static int BinarySearchCountAll<T>(this List<T> myList, T searchValue)
{
int count = 0,
int center = myList.BinarySearch(searchValue);
if ( center < 0 ) return count;
for ( int k = center + 1; k < myList.Length - 1 && myList[k] = searchValue; ++k )
++count;
for ( int k = center - 1; k >=0 && myList[k] = searchValue; --k )
++count;
return count;
}
最佳答案
你是对的
while (left < 0 && myList[left-1].Equals(searchValue))
应该是
while (left > 0 && myList[left-1].Equals(searchValue))
相反。 注意右边的对称性:while (right < (myList.Count - 1)....自然暗示它应该大于左边。
BinarySearchCountAll 方法找到一个索引“center”,其中 center=searchValue。由于列表已排序,它可以简单地遍历相邻元素,直到它们不等于“中心”。然后,它返回相等的“中心”元素的数量
关于c# - 请帮助我理解我书中的这个 "BinarySearchCountAll"方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36254383/