Алгоритм пикового поиска 1D в Python с использованием функции «разделяй и властвуй»

Question

Я пытаюсь реализовать алгоритм пика 1D в python, хотя у меня возникают проблемы с его реализацией. Идея состоит в том, что он сравнивает центральный член массива и выбирает сторону с более высоким соседним членом. Эта половина становится новым массивом. Только когда центральным является самый большой термин, он становится вершиной. Вот мой код: import math

import math

array = [1,2,3,4,5,6,7]
size = len(array)
count = 0

while count == 0: 
    if len(array) == 2:
        count += 1
        print(max(array[0],array[1])) 
        break
    elif count == 0: 
        elif array[math.floor(abs(size/2))] < array[math.floor(abs(size/2))-1]:
            new_array = [] 
            for i in range(int(abs(size)/2)):
                new_array.append(array[i])
                array = new_array
        elif array[math.floor(abs(size/2))] < array[math.floor(abs(size/2))+1]:
            new_array = []
            for j in range(math.floor(abs(size)/2),size): 
                new_array.append(array[j])
            array = new_array
        elif count == 0: 
            count += 1
            print(array[math.floor(abs(size/2))])
            break

Я продолжаю получать ошибки, и я не могу определить проблему. Кто-нибудь может помочь?

Answer 1

Другая проблема (кроме уловки compuphy) заключается в том, что вы не меняете переменную «size» при изменении размера массива, что может привести к IndexErrors. Кроме того, несколько мелочей:

1. Нет смысла делать пресс (размер / 2), так как он всегда будет положительным.
2. Вместо пола (размер / 2), если это python 3, просто сделайте size // 2 для целочисленного деления, или если это python 2, достаточно будет size / 2.
3. От того, как реализована ваша программа, время выполнения больше, чем O (logN), который, как я полагаю, вы нацеливаете, поэтому я думаю, что вам следует изучить реализации, в которых вы сохраняете верхнюю и нижнюю границу искомого массива, а не создаете новый массив в каждой итерации.

Answer 2

У вас есть elif в первом elif условии, но без каких-либо предшествующих if's :

elif count == 0: 
        elif array[math.floor(abs(size/2))] < array[math.floor(abs(size/2))-1]:
        ^^^^

попробуйте изменить их на if