Алгоритм нахождения первого большего целого числа с o-small (n) сложностью

Question

Мне нужно написать алгоритм, который найдет первое целое число, которое больше x в отсортированном массиве, где могут повторяться целые числа.Алгоритм должен иметь сложность o (n), где o мало.В чем разница между алгоритмами с O (n) и o (n) сложностью?

Answer 1

Вот очень хорошее и подробное объяснение нотации «большой-против-маленькой»: Разница между нотацией «большой-о» и «маленькая-о»

Самый простой, но эффективный алгоритмБинарный поиск, как упомянуто @OmG, и вот ссылка для запуска: https://en.wikipedia.org/wiki/Binary_search_algorithm

Идея довольно проста: вы просто сравниваете искомое число со средним элементом массива, если серединаменьше вашего номера очевидно, что вам нужно найти в правой половине, ... в противном случае в левой половине.Вы останавливаетесь, когда есть только один элемент.

Answer 2

Как люди указывали до меня, вы хотите выполнить бинарный поиск.Этот пост включает пример кода:

В Python это проще всего с функцией деления на две части: https://docs.python.org/2/library/bisect.html

from bisect import bisect_right

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

Answer 3

Вы можете использовать метод двоичного поиска, чтобы найти первое наибольшее целое число x.Это было бы в O(log(n)) = small_o(n).