如何在二分查找时处理空值？

Question

在对 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的新列表并不可行。

- wes

Answer 1

除非确实需要选择/查找 null 值（不确定什么意思，因为 null 是单例的，并且在唯一值上执行二分搜索通常是最理想的），否则考虑根本不允许它们存在于列表中。

---

[上一个答案：在更深入思考问题后，我决定 null 很可能没有在问题空间中的位置。根据需要进行微调。]

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

这应该不会有太大的影响，因为排序已经是必须的。如果将项目更改为 null -- 这听起来像是一个讨厌的副作用！-- 然后只需“压缩”列表（例如，“删除” null 条目）。但是，除非有充分的理由，否则最好不要修改排序后的列表。

二分搜索只适用于（完全）排序的数据。没有把它变成一个二进制-也许线性搜索的意义。

愉快编码。

- user166390

---

我添加了一些关于为什么我不能使用简单的线性搜索和为什么我不能预处理列表的信息。 - wes