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?

Politicize

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

Hollister

Can you please proceed with the above example, finding 2 in the above sequence. and derive a solution in O(logn) – Politicize

Hmmm ... the problem here is finding the maximum in O(logn). The rest is as you mentioned – Embayment

@AndyStowAway I thought this was clear (to the OP). Edited my answer. – Hollister

Please note that the sequence is monotonic. So there can be duplicates. Thus finding maximum with your logic would not work. – Finicking

Answer 2

As I remember the best search for the arrays which elements are ordered increasing and then decreasing is the Fibonacci search algorithm.

Earleneearley

Answer 3

Here is a sketch in python. In short we are aiming to find an element which borders the increasing and decreasing regions (this we check we two conditions checking the neighbor elements). And we keep hopping like in standard binary search until we find this element. Hope that helps.

def get_max(arr):
    if len(arr) == 1:
         return arr[0]
    if len(arr) in [0,2]:
        return None
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left+right) // 2
        #increasing region
        if arr[mid+1] >  arr[mid] and arr[mid] > arr[mid-1]:
            left = mid + 1
        #decreasing region
        elif arr[mid+1] < arr[mid] and arr[mid] < arr[mid-1]:
            right = mid - 1
        elif arr[mid+1] < arr[mid] and arr[mid-1] > arr[mid]:
            return arr[mid-1]
        else:
            return arr[mid]
    return -1

Oblate