在二进制搜索期间如何处理空值？

Question

null在对a进行二进制搜索期间处理s 的最佳方法是什么List<string>（嗯，如果我可以事先读取所有值，那将是一种方法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()缓存了它检索的值。有没有一种更简单的方法，而无需列出非空值的中间列表（由于GetItem()上面的函数很慢，我的目的花费的时间太长了）？

我想我想问的是，是否有比降级为线性搜索更智能的方法来处理空值。极有可能只有一小部分的空值（1-5％），但是有可能存在100个空值序列。

编辑-数据看起来像这样

         aa aaa
b bb bbb
抄送
d ddd

其中的每一行都是一个单独的对象，并非所有单元格都可以保证被填充。用户需要能够在整个行中进行搜索（以便“ bb”和“ bbb”都将与整个第二行匹配）。查询每个对象的速度非常慢，以至于线性搜索将无法进行。出于同样的原因，创建没有空值的新列表实际上是不可行的。

Answer 1

除非有理由实际选择/查找一个null值（不确定这意味着什么，因为null单例和二分搜索通常最适合唯一值），请考虑根本不允许它们出现在列表中。

[先前的答案：在对这个问题进行了更多思考之后，我认为nulls 可能在问题空间中没有位置——适当地采用一些片段。]

如果需要空值，只需对列表进行排序，使空值位于第一个（或最后一个）并正确更新逻辑 - 然后确保不要对任何值调用方法null;-)

这应该不会产生什么总体影响，因为已经需要进行排序。如果项目被更改为null——这听起来像是一个令人讨厌的副作用！-- 然后只需“压缩”列表（例如“删除”空项）。但是，除非有充分的理由，否则我不会修改排序列表。

二分搜索仅真正设计/适合（完全）排序的数据。将其变成二进制的线性搜索是没有意义的。

快乐编码。