binary_1D_peak_en.py

def binary_search_1D_peak(arr): #1D integer array as input
    if len(arr) == 0:
        return None
    if len(arr) == 1:
        return 0 #1 element array is treated specially
    arr_start = 0
    arr_end = len(arr) - 1
    while True:#let's use divide and conquer approach
        check_coord = (arr_start + arr_end) // 2 #select array middle element, check for local maximum
        cur_value, left_value, right_value = arr[check_coord], arr[check_coord], arr[check_coord]
        if check_coord - 1 >= arr_start:
            left_value = arr[check_coord - 1]
            if left_value > cur_value: #go to the left if the growth direction is to the left
                arr_end = check_coord - 1 #udate size of the task - we divided it to smaller parts
                continue
        if check_coord + 1 <= arr_end:
            right_value = arr[check_coord + 1]
            if right_value > cur_value: #go to the right if there is growth to the right
                arr_start = check_coord + 1 #update the size of the task - we divided it to smaller parts
                continue
        #no growth at all - return the answer then
        return check_coord

################################################################
############## Let's do some tests: ############################
################################################################
import random
import time
print('Random test:') #random array test
arr = [random.randint(-100,100) for _ in range(1000000)]
start = time.time() #measure execution time
for N in range(10000): #10000 repeats to measure time
    peak_coord = binary_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 in the end of array
arr = [i for i in range(10000)]
start = time.time()#measure execution time
for N in range(10000): #10000 repeats to measure time
    peak_coord = binary_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: 1 Peak element: 91 Left element: 2 Right element: 23
##9999 repeats, search time: 0.018000364303588867
##Worst case:
##Peak coordinate: 9999 Peak element: 9999 Left element: 9998 Right element: None
##9999 repeats, search time: 0.07501578330993652
################################################################