是否有一种算法可以在排序数组中搜索不包括一个复杂度为 O(lgn) 的指定数字的元素？

Question

让

int arr[]={0,1,2,-1,4,8,9,-1,17,32,56,128};

数组排序不包括指定数-1，我想在array.So中搜索一个元素（不是指定数）有没有满足以下条件的算法？

1. 时间复杂度为O(lgN)
2. 如果该元素不存在于数组中，return适当的插入位置。
3. 将指定号码作为空位，return值可以是指定号码的位置

例如如果我想在前面的数组中搜索 10，那么 return 值将是 7.

提前致谢。

Answer 1

是的。您只会增加搜索 -1 的复杂性，这将小于 O(log n)。

可以用另外一个数组映射上一个数组中-1的位置

Answer 2

没有，只看长度为n的数组，其中所有的数字都是-1（你指定的数字）。现在随机 select 一个位置并将其替换为其他数字。基本上你的数组看起来像这样：

[-1, -1, -1, -1, -1, -1, 8, -1, -1, -1, -1, -1, -1, -1, -1]

现在您无法使用 O(log N) 元素确定性地找到数字 8 的位置。

---

所以不，一般情况下你不能这样做。但是如果指定元素的个数真的很少，我相信你可以修改二分查找来处理这种情况。

Answer 3

这取决于你是否能负担得起 O(N) 的额外存储空间，以及 O(N) 的预处理步骤。

如果可以，您可以为有意义的元素创建索引（例如，指向非 -1 元素的指针数组）。这需要 O(N) time/space，但是一旦你有了它，你就可以使用 if 来搜索具有 O(log n) 复杂度的真实集合，就像你没有 "dead" 个条目。