Finding an number in montonically increasing and then decreasing sequencecera

Question

Finding the maximum or minimum value in a sequence that increases montonically and then decreases monotonically can be done in 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)?

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

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.

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

Answer 1

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).

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).

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).