Определите, увеличивается ли массив O (log (n)), и найдите значение "switch" - PullRequest
Новая
       75

Определите, увеличивается ли массив O (log (n)), и найдите значение "switch"

0 голосов
/ 28 мая 2020

Я пытаюсь определить, сначала уменьшается массив, а затем увеличивается. Также мне нужно узнать значение, когда шаблон изменяется с возрастания на убывание, которое будет минимальным значением в массивах

Скажем, например, у меня есть следующий массив:

[10, 10, 10, 10, 10, 10, 8, 8, 8, 6, 6, 6, 6, 6, 4, 3, 12, 13, 22, 31, 40, 59, 78]

и этот

[- 1, 1, 2, 4, 8, 16, 32, 64]

Редактировать: для простоты вы можете предположить, что значения не будут повторяться, как первые Пример, который я вам показал

Я в основном хочу написать программу, которая занимает время O (logn). Я пытаюсь использовать двоичный поиск, и это то, что я придумал. Входом в функцию является отсортированный список или список по убыванию-возрастанию. Это может иметь повторяющиеся значения, как показано в приведенных выше примерах. 

    def find_middle(ls):
        start = 0
        end = len(ls) - 1
        idx = -1
        while start < end:
            mid = start + (end - start) // 2
            middle = ls[mid]
            if ls[mid-1] <= middle and middle > ls[mid+1]):   
                return middle
            elif ls[mid-1] < middle:
                start = mid         
            else:
                end = mid
     return idx

Извините за беспорядочный код, я много с ним повозился, и на данный момент я только что отказался от поиска решения.

Если массив ТОЛЬКО уменьшается или увеличивается, я хочу, чтобы функция возвращала -1.

Любая помощь будет принята с благодарностью!

1 Ответ

0 голосов
/ 28 мая 2020

В вашем примере повторение. Без повторения это легко. Проверьте значения по трем различным индексам. Называя эти x, y и z, мы видим, что граница может быть только в одном из трех интервалов (x, y), (y, z), (z, x). Итак, если мы посмотрим на порядок этих пар, либо 2 будут по возрастанию, а 1 по убыванию, либо наоборот. Большинство совпадает с массивом. Затем вы можете использовать двоичный поиск, чтобы найти границу. Это O (log n)

При повторении это требует (в худшем случае) линейного времени. Плохой пример - массив, в котором все элементы, кроме двух, идентичны. В этом случае O (n) просто найти разные элементы. В общем, при повторении применяется тот же алгоритм, но вам нужно дополнительно поработать по поиску различных элементов.

...