发现在montonically增加一个数字，然后降低sequencecera [英] Finding an number in montonically increasing and then decreasing sequencecera

问题描述

查找在序列中增加montonically的最大值或最小值，然后减小单调可以在O完成（log n）的。

Finding the maximum or minimum value in a sequence that increases montonically and then decreases monotonically can be done in O(log n).

不过，如果我要检查，如果在这样的序列存在一个数字，可这也可以为O完成（log n）的？

However, if i want to check if a number exists in such a sequence, can this also be done in O(log n)?

我不认为这是可能的。考虑这个例子：1 4 5 6 7 10 8 3 2 0

I do not think that is possible. Consider this example: 1 4 5 6 7 10 8 3 2 0.

在这个例子中，如果我需要找到序列是否包含2，我没有任何条件来划分搜索空间分成一半的原始搜索空间。在最坏的情况，情况下，它会为O（n），因为你需要检查两半，当我们试图寻找2。

In this example, if I need to find whether the sequence contains '2', I do not have any conditions to divide the search space into half of the original search space. In the worst, case it will be O(n), as you need to check for both halves, when we are trying to search for 2.

我想知道，如果这种搜索在O完成（log n）的时间？

I would like to know, if this search be done in O(log n) time?

推荐答案

正如你提到的，你可以找到在O（LOGN）的最大值（和它的位置）。然后，你可以做的每一个部分，这也是一个二分查找O（LOGN）。

As you noted, you can find the maximum (and its position) in O(logn). Then you can just do a binary search in each part which is also O(logn).

在上面的例子中，可以找到最大10在5位。 然后，你做的序列[0..5]（1，4，5，6，7，10）二进制搜索。 作为2没有发现，则继续执行中的其他部分的二进制搜索（10，8,3，2,0）。

In the above example, you find the maximum 10 at position 5. Then you do a binary search in the subsequence [0..5] (1, 4, 5, 6, 7, 10). As 2 is not found, you proceed to do a binary search in the other part (10, 8, 3, 2, 0).

要找到在澳最大（LOGN）：看这两个元素为中心：7＆LT; 10.因此，我们仍然在增加部分和必须寻找最大的序列的右半：（10，8,3，2,0）。看看8和3的进行左侧部分（10,8）。

To find the maximum in O(logn): look at the two elements at the center: 7 < 10. So we are still in the increasing part and have to look for the maximum in the right half of the sequence: (10, 8, 3, 2, 0). Look at 8 and 3 an proceed with the left part (10, 8).

这篇关于发现在montonically增加一个数字，然后降低sequencecera的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！