是否存在搜索排序数组中元素的算法,不包括复杂度为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的位置.

所以不,一般情况下你不能这样做.但是如果指定元素的数量非常小,我相信你可以修改二进制搜索来处理这种情况.