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

Question

让

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

数组排序不包括指定数-1，我想在数组中查找一个非指定数的元素，请问有满足以下条件的算法吗？

1. 时间复杂度为O(lgN)
2. 如果数组中不存在该元素，则返回合适的插入位置。
3. 将指定数字作为一个空槽，返回值可以是指定数字的位置。

例如如果我想在前面的数组中查找10，那么返回值就是7。

提前致谢。

Answer 1

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

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

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

---

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