binary_row_2D_peak_en.py

def find_max_in_a_row(arr, row_num): #helper function to find max in a row (not a peak, but maximum!)
    cur_max = arr[row_num][0]
    cur_max_pos = 0
    for i in range(1, len(arr[row_num])):
        if arr[row_num][i] > cur_max:
            cur_max = arr[row_num][i]
            cur_max_pos = i
    return cur_max_pos

def row_binary_search_2D_peak(arr): #2D array of integers as input
    if len(arr) == 0 or (len(arr) == 1 and len(arr[0]) == 0):
        return None
    if (len(arr) == 1 and len(arr[0]) == 1):
        return (0,0) #empty array and array of 1 element as corner cases
    start_x, start_y = 0, 0
    end_x, end_y = len(arr) - 1, len(arr[0]) - 1
    while True: #use divide and conquer
        check_row = (start_x + end_x) // 2 #select middle row
        check_col = find_max_in_a_row(arr, check_row) #search for max in a row
        cur_value, top_value, bottom_value = [arr[check_row][check_col]] * 3 #initialize 3 variables
        if check_row - 1 >= start_x:#search for growth direction
            top_value = arr[check_row - 1][check_col]
            if top_value > cur_value:
                end_x = check_row - 1
                continue
        if check_row + 1 <= end_x:#search for growth direction
            bottom_value = arr[check_row + 1][check_col]
            if bottom_value > cur_value:
                start_x = check_row + 1
                continue
        #no growth - peak is found
        return (check_row, check_col)

################################################################
############## Let's run some tests: ###########################
################################################################
import random
import time
n, m = 100, 100
print('Random test:') #random data test
arr = [[] for _ in range(n)]
for i in range(n):
    arr[i] = [random.randint(-100,100) for _ in range(m)]
start = time.time()#measure execution time
for N in range(10000): #10000 repeats to track time
    peak_coord = row_binary_search_2D_peak(arr)
end = time.time()
peak_element, left_element, right_element, top_element, bottom_element = arr[peak_coord[0]][peak_coord[1]], None, None, None, None
if peak_coord[0] > 0:
    top_element = arr[peak_coord[0] - 1][peak_coord[1]]
if peak_coord[0] < len(arr) - 1:
    bottom_element = arr[peak_coord[0] + 1][peak_coord[1]]
if peak_coord[1] > 0:
    left_element = arr[peak_coord[0]][peak_coord[1] - 1]
if peak_coord[1] < len(arr[0]) - 1:
    right_element = arr[peak_coord[0]][peak_coord[1] + 1]
print('Peak coordinate:', peak_coord,'Peak element:', peak_element, 'Left element:', left_element, 'Right element:', right_element, 'Top element:', top_element, 'Bottom element:', bottom_element)
print(N, 'repeats, search time:', end - start)

print('Worst case:') #worst-case test
arr = [[] for _ in range(n)]
counter = 0
for i in range(0,n,2):
    if (counter//2) % 2 == 0:
        arr[i] = [i for i in range(m*counter, m*(counter+1))]
        arr[i+1] = [i for i in range(m*counter, m*(counter+1))]
        arr[i+1][-1] += 1
        counter += 2
    else:
        arr[i] = [i for i in range(m*(counter+1),m*(counter),-1)]
        arr[i+1] = [i for i in range(m*(counter+1),m*(counter),-1)]
        arr[i+1][0] += 1
        counter += 2
start = time.time()#measure execution time
for N in range(10000): #10000 repeats to track time
    peak_coord = row_binary_search_2D_peak(arr)
end = time.time()
peak_element, left_element, right_element, top_element, bottom_element = arr[peak_coord[0]][peak_coord[1]], None, None, None, None
if peak_coord[0] > 0:
    top_element = arr[peak_coord[0] - 1][peak_coord[1]]
if peak_coord[0] < len(arr) - 1:
    bottom_element = arr[peak_coord[0] + 1][peak_coord[1]]
if peak_coord[1] > 0:
    left_element = arr[peak_coord[0]][peak_coord[1] - 1]
if peak_coord[1] < len(arr[0]) - 1:
    right_element = arr[peak_coord[0]][peak_coord[1] + 1]
print('Peak coordinate:', peak_coord,'Peak element:', peak_element, 'Left element:', left_element, 'Right element:', right_element, 'Top element:', top_element, 'Bottom element:', bottom_element)
print(N, 'repeats, search time:', end - start)
#################################################################
############## Output example: ##################################
##Random test:
##Peak coordinate: (49, 8) Peak element: 99 Left element: -53 Right element: -22 Top element: 28 Bottom element: 68
##9999 repeats, search time: 0.06327033042907715
##Worst case:
##Peak coordinate: (99, 0) Peak element: 9901 Left element: None Right element: 9899 Top element: 9900 Bottom element: None
##9999 repeats, search time: 0.5138230323791504
################################################################