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

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

• python
• binary-search

• 1 This question is similar to: Pythonic way to find maximum value and its index in a list?. If you believe it’s different, please edit the question, make it clear how it’s different and/or how the answers on that question are not helpful for your problem. – John Carter Commented Jan 20 at 18:07
• The code you posted is a binary search, so it only works if the input is sorted. – Barmar Commented Jan 20 at 18:24
• I agree, but even if the given array is passed, it is working fine. I wanted to know how this code is working with above code. – Prasun Commented Jan 20 at 18:25
• I don't think it does. It might work by accident for that test case, but not more generally. – Barmar Commented Jan 20 at 18:26
• If you want to figure out why it's getting the right answer for that input, step through it in a debugger. – Barmar Commented Jan 20 at 18:27

2 Answers 2

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.

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.