在对 List<string>
进行二分查找时,如何处理 null
值是最佳方式?(如果我事先可以读取所有值,那么它将是一个 List<string>
)
int previous = 0;
int direction = -1;
if (itemToCompare == null) {
previous = mid;
for (int tries = 0; tries < 2; tries++) {
mid += direction;
itemToCompare = GetItem(mid);
while (itemToCompare == null && insideInclusiveRange(min, max, mid)) {
mid += direction;
itemToCompare = GetItem(mid);
}
if (!insideInclusiveRange(min, max, mid)) {
/* Reached an endpoint without finding anything,
try the other direction. */
mid = previous;
direction = -direction;
} else if (itemToCompare != null) {
break;
}
}
}
我目前正在做类似上面的事情——如果遇到null,则线性搜索直到遇到非null或超出端点,如果没有成功,则在另一个方向上重复。在实际代码中,我从先前的比较结果中获取
direction
,而GetItem()
缓存它检索到的值。是否有一种更简单的方法,而不是制作非null值的中间列表(因为上面的GetItem()
函数很慢,所以这需要花费太长时间)?我想知道是否有一种更聪明的处理null值的方法,而不是退化为线性搜索。很可能只有很小一部分为null(1-5%),但可能存在100个null的序列。
编辑-数据看起来像这样
aa aaa b bb bbb c cc d ddd其中每行都是单独的对象,并且不能保证填充所有单元格。用户需要能够跨整行搜索(因此第二行的“bb”和“bbb”都将匹配)。查询每个对象的速度足够慢,线性搜索无法工作。出于同样的原因,创建一个没有null的新列表并不可行。