Finding an number in montonically increasing and then decreasing sequencecera

user_234495 0
Viewed 3041

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?

binary-search c algorithm
3 Answers

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
user_10699420
Related