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

Question

处理的最佳方式是什么 null 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;
        }
    }
}

我目前正在做类似上面的事情 - 如果遇到空值，则在一个方向上线性搜索，直到遇到非空值或超出端点，如果没有成功，则在其他方向重复。在实际代码中我得到 direction从之前的比较结果，还有 GetItem()缓存它检索的值。有没有更简单的方法，而不需要制作非空值的中间列表(对我来说需要太长时间，因为上面的 GetItem() 函数很慢)？

我想我在问是否有比降级为线性搜索更聪明的方法来处理空值。很可能只有一小部分空值 (1-5%)，但可能会有 100 个空值序列。

编辑 - 数据看起来像这样

啊啊啊
呜呜呜呜
cc
滴滴

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

Answer 1

除非有理由实际选择/查找 null值(不确定这是什么意思，因为 null 是一个单例，并且二进制搜索通常是对唯一值最理想的)，请考虑根本不允许它们出现在列表中。

[ 上一个答案:在对问题进行更多思考后，我决定null s 可能在问题空间中没有位置——适本地取一些零碎的部分。]

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

这应该几乎没有整体影响，因为已经需要排序。如果项目更改为 null ——这听起来像是一个令人讨厌的副作用! - 然后只是“压缩”列表(例如“删除”空项目)。但是，除非有充分的理由，否则我不会修改排序列表。

二分搜索仅真正设计/适用于(完全)排序的数据。将其转换为二元可能线性搜索毫无意义。

快乐编码。