Finding peak point in an array by using divide and conquer approach

Question

It is to find the maximum element in an array which is first increasing and then decreasing. I've tried to write my idea by using divide and conquer approach. Is there any improvable or missing point? My code is following,

def search(arr, low, high):
    if low == high:
        return arr[low]

    mid = low + (high - low) // 2

    if arr[mid] > arr[mid + 1]:
        # if it's peak that a number whose left and right are smaller than it, return it
        if arr[mid] > arr[mid - 1]:
            return arr[mid]
        else:
            return search(arr, low, mid)
    else:
        return search(arr, mid + 1, high)


if __name__ == "__main__":
    arr = [ 70, 80, 9, 6 ]
    arr2 = [60, 70, 72, 74, 88]
    arr3 = [8, 10, 20, 80, 100, 200, 400, 500, 3, 2, 1]
    arr4 = [10, 20, 30, 40, 50]
    arr5 = [1, 3, 50, 10, 9, 7, 6]
    arr6 = [120, 100, 80, 20, 0]

    print(search(arr, 0, len(arr) - 1))
    print(search(arr2, 0, len(arr2) - 1))
    print(search(arr3, 0, len(arr3) - 1))
    print(search(arr4, 0, len(arr4) - 1))
    print(search(arr5, 0, len(arr5) - 1))
    print(search(arr6, 0, len(arr6) - 1))

Output:

AJNeufeld · Accepted Answer · 2019-01-08 01:16:46Z

The code will crash with an out of bounds exception if given a zero-length array.

You are playing a little loose with the array endpoints. If you get to mid=0, and it turns out that arr[mid] > arr[mid+1], then you will check arr[mid] > arr[mid-1], which will be reading arr[-1] which is the element at the other end of the array. Fortunately, if arr[0] > arr[1], then the array must be monotonically decreasing, and the last value will be the smallest, but relying on that is tricky behaviour.

Your code is recursively executing return search(...), Python does not do tail-recursion-optimization. This could could easily be re-written to use a loop, which would be faster and doesn’t require any additional stack space. For example, something like:

while low < high:
    mid = low + (high - low) // 2

    if arr[mid-1] < arr[mid] < arr[mid+1]:
        return arr[mid]

    if arr[mid] > arr[mid+1]:
        high = mid
    else:
        low = mid + 1

return arr[low]

You search(mid+1, high). Why don’t you search(low, mid-1)? Seems asymmetrical.

Minor nit: You algorithm will fail if the array can have equal elements, such as 5, 50, 10, 10, 10, 10, 5. It will find “10” at the mid-point and on both sides, at which point it will drift to the larger indexes, and eventually declare “10” as the maximum.

Stack Exchange Network

Finding peak point in an array by using divide and conquer approach

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Finding peak point in an array by using divide and conquer approach

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions