linear_1D_peak_en.py

def linear_search_1D_peak(arr): #input - 1D array of integers
    if len(arr) == 0:
        return None
    if len(arr) == 1:
        return 0 #If array is 1-element long we make special return case
    for i in range(len(arr)):
        if ((i == 0) and arr[i] >= arr[i+1]) or ((i == len(arr) - 1) and arr[i-1] <= arr[i]):
            return i #Corner cases (written in such way only for convinience of code-reading)
        if arr[i] >= arr[i-1] and arr[i] >= arr[i+1]:
            return i #Peak condition - return local maximum


################################################################
############## Let's run some tests ############################
################################################################
import random
import time
print('Random test:') #this will be a test on random array
arr = [random.randint(-100,100) for _ in range(1000000)]
start = time.time()#measure execution time
for N in range(10000): #10000 times repeat to be able to measure required time
    peak_coord = linear_search_1D_peak(arr)
end = time.time()
peak_element, left_element, right_element = arr[peak_coord], None, None
if peak_coord > 0:
    left_element = arr[peak_coord - 1]
if peak_coord < len(arr) - 1:
    right_element = arr[peak_coord + 1]
print('Peak coordinate:', peak_coord,'Peak element:', peak_element, 'Left element:', left_element, 'Right element:', right_element)
print(N, 'repeats, search time:', end - start)

print('Worst case:') #worst-case test, peak is just in the end of the array
arr = [i for i in range(10000)]
start = time.time()#measure execution time
for N in range(10000): #10000 repeats again, to measure time
    peak_coord = linear_search_1D_peak(arr)
end = time.time()
peak_element, left_element, right_element = arr[peak_coord], None, None
if peak_coord > 0:
    left_element = arr[peak_coord - 1]
if peak_coord < len(arr) - 1:
    right_element = arr[peak_coord + 1]
print('Peak coordinate:', peak_coord,'Peak element:', peak_element, 'Left element:', left_element, 'Right element:', right_element)
print(N, 'repeats, search time:', end - start)

##################################################################
############## Output examples: ##################################
##Random test:
##Peak coordinate: 2 Peak element: 66 Left element: 62 Right element: 43
##9999 repeats, search time: 0.016994476318359375
##Worst case:
##Peak coordinate: 9999 Peak element: 9999 Left element: 9998 Right element: None
##9999 repeats, search time: 27.356966972351074
################################################################