vam*_*msi 10 c algorithm binary-search
找到以单调方式增加然后单调减小的序列中的最大值或最小值可以在O(log n)中完成.
但是,如果我想检查一个数字是否存在于这样的序列中,那么这也可以在O(log n)中完成吗？
我不认为这是可能的.考虑这个例子:1 4 5 6 7 10 8 3 2 0.
在这个例子中,如果我需要查找序列是否包含'2',我没有任何条件将搜索空间划分为原始搜索空间的一半.在最糟糕的情况下,它将是O(n),因为当我们试图搜索2时你需要检查两半.
我想知道,如果这个搜索是在O(log n)时间完成的吗？
Hen*_*rik 12
如您所述,您可以在O(logn)中找到最大值(及其位置).然后你可以在每个部分进行二进制搜索,也就是O(logn).
在上面的示例中,您在位置5处找到最大值10.然后在子序列[0..5](1,4,5,6,7,10)中进行二分查找.如果未找到2,则继续在其他部分(10,8,3,2,0)中进行二分查找.
要找到O(logn)中的最大值:看看中心的两个元素:7 <10.所以我们仍然在增加部分,并且必须在序列的右半部分寻找最大值:(10,8 ,3,2,0).看8和3,继续左侧部分(10,8).