linear_2D_peak_en.py

def linear_search_2D_peak(arr): #2D array n times m 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) #special cases - empty array and array of one element
    x, y = 0, 0 #suppose we start from top left corner
    while True:
        x_offsets = []
        y_offsets = []#collect all possible neighbours that should be checked
        cur_best_coord = (x,y)
        cur_best_val = arr[x][y]
        if x == 0:
            x_offsets = [x+1]
        elif x == len(arr) - 1:
            x_offsets = [x-1]
        else:
            x_offsets = [x-1, x+1]
        if y == 0:
            y_offsets = [y+1]
        elif y == len(arr) - 1:
            y_offsets = [y-1]
        else:
            y_offsets = [y-1, y+1]
        for x_offset in x_offsets: #select largest growth direction
            if arr[x_offset][y] > cur_best_val:
                cur_best_coord = (x_offset,y)
                cur_best_val = arr[x_offset][y]
        for y_offset in y_offsets:
            if arr[x][y_offset] > cur_best_val:
                cur_best_coord = (x,y_offset)
                cur_best_val = arr[x][y_offset]
        if cur_best_coord != (x,y): #if it is not yet a peak - move to largest growth direction
            x,y = cur_best_coord
        else:
            return (x,y) #if it is a peak - return

################################################################
############## Let's make some tests: ##########################
################################################################
import random
import time
n, m = 100, 100
print('Random test:') #random array 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 repeat to track time
    peak_coord = linear_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 = linear_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: (0, 0) Peak element: 52 Left element: None Right element: -62 Top element: None Bottom element: 0
##9999 repeats, search time: 0.007973194122314453
##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: 45.12544012069702
################################################################