CODEWITHSUNDEEP
pythonbinary-search
Prasun
Prasun

Reputation: 109

How does this code manage to correctly find the peak element's array index using binary search on an unsorted array?

The below code is using binary search. Since the array is not sorted, how does it manage to correctly figure out the peak element's index? Generally it works on sorted arrays only, right?

Input: arr = [0,10,5,2]

Output: 1

def peakIndexInMountainArray(arr: List[int]) -> int:
    l = 0
    h = len(arr) - 1
    while l < h:
        mid = l + (h - l) // 2
        if arr[mid] > arr[mid + 1]:
            h = mid
        else:
            l = mid + 1
    return l

Upvotes: 0

Views: 103

Answers (2)

user2357112
user2357112

Reputation: 281748

The basic idea of binary search, "split the input and pick the correct half", works for more use cases than just finding a specific element of a sorted array. It works for any problem where you're trying to find a thing, and you can quickly determine which half of the input it's in without needing to search each half.

In this case, you're trying to find the max element of an array that's strictly ascending, then strictly descending (so no adjacent duplicates). So if you look at the element in the middle, and it's greater than the element directly to its right, then you know it's going to be greater than all elements to the right. The max must be in the left half.

On the other hand, if it's smaller than the element to its right, then all elements to the left must also be smaller. The max must be in the right half, so you look in that half.

Upvotes: 2

mkrieger1
mkrieger1

Reputation: 23251

The assumption appears to be that the values in the array are strictly increasing from the beginning up to a maximum value, and then strictly decreasing until the end.

As such, the condition arr[mid] > arr[mid + 1] (i.e. two neighboring values are decreasing) will be false (or 0) in the first part of the array and true (or 1) in the second part of the array.

So effectively this is searching the transition from 0 to 1 in an array like [0, ..., 0, 0, 1, 1, ..., 1]. Since this is a sorted array, binary search will work.

Upvotes: 0

Related Questions