2D peak finding binary search

Question

Taken from mit 6.006 : To find a peak in a 2D array, where a number is a peak if it is >= than all its neighbours:

Pick middle column j = m/2
Find global maximum on column j at (i, j)
Compare (i, j − 1),(i, j),(i, j + 1)
Pick left columns of (i, j − 1) > (i, j), Similarly for right
(i, j) is a 2D-peak if neither condition holds
Solve the new problem with half the number of columns.
When you have a single column, find global maximum and you‘re done.

I understand why it might find a peak, but I think it only finds a peak on half of the array if it exists

Using binary search here confuses me since (1) the 2d array is not sorted, and each time you halve you are essentially saying there can be no peak on the left(which is not confirmed?)
It finds the maximum element in the middle column - This ignores the possibility of a peak formed from non-maximal numbers, or that you can have more than one 1D peak in that column
They compare numbers to the left and right of the max of the middle column - this discounts that there may be elements in the left and right column that are larger than max but not adjacent

Can someone explain to me why this algorithm is correct, hopefully by explaining (1)(2)(3)

user_2144669 · Answer

each time you halve you are essentially saying there can be no peak on the left

Ah, no, we're saying that there is a peak on the right. There can be peaks on the left too, but we don't need to find every peak.

To prove that there is a peak on the (without loss of generality) right, consider the following "gradient ascent" algorithm:

Start at an arbitrary number.
While the current number has at least one greater neighbor, go to an arbitrary greater neighbor.

This algorithm never cycles because the current number only increases. This algorithm hence terminates because there are finitely many numbers. When the algorithm terminates, it has found a peak.

Consider what happens if (i, j) has the maximum value in its column and we start gradient ascent at (i, j). Either (i, j) is a peak (great!), or we move to a greater number in one of the adjacent columns. In the latter case, this number is greater than the maximum in column j, hence greater than every number in column j. Therefore, gradient ascent will never reenter the column, and thus it will never enter the columns on the other side, implying the existence of a peak on the desired side.

user_17479334 · Answer

The idea of using binary search to find peak elements in a matrix is very good. But if used alone, it returns only one peak element (this value is generally not the maximum). You can use the following code to find all the peak elements by binary search method.

def Div(lst, low, high, c):
    mid = (low + high)//2
    if low > high:
        return ""
    else:
        if mid+1 < len(lst) and lst[mid][c] > lst[mid+1][c] and lst[mid][c] > lst[mid -1][c] and lst[mid][c] > lst[mid][c + 1] and lst[mid][c] > lst[mid][c - 1]:
            return str(lst[mid][c]) + " " + Div(lst, low, mid-1, c) + Div(lst, mid+1, high, c)
        else:
            return Div(lst, low, mid-1, c) + Div(lst, mid + 1, high, c)
def peak(lst, c):
        return Div(lst, 0, len(lst), c)
lst=[[0,0,0,0,0,0],
     [0,0,1,0,4,0],
     [0,2,0,3,0,0],
     [0,0,5,0,6,0],
     [0,0,0,0,0,0]]
for i in range (0,5):
    print(peak(lst,i))

output: 2 1 5 3 4 6

O(mn)

2D peak finding binary search

2 Answers