Поиск первого четного числа в списке со сложностью алгоритма лучше, чем линейный

Question

У меня есть список с сначала нечетными элементами, а затем четными, поэтому сначала в списке появляются нечетные элементы, а затем - четные элементы. Например:

list = [5,99,3,7,111,13,4,24,4,8]

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

Answer 1

Поскольку значения уже организованы, просто возьмите середину коллекции (массив, список) и проверьте, является ли это четное или нечетное значение.

Это четное? Тогда первые четные значения находятся в первой половине коллекции, и вы можете отменить вторую половину или текущую.

Это странно? Тогда первое четное значение еще не пришло, отбросьте первую половину, оставьте вторую как свою новую коллекцию и продолжайте делать это, пока не найдете ее.

Некоторое визуальное руководство: https://www.freecodecamp.org/news/binary-search-in-python-visual-introduction/

Answer 2

Python модуль bisect поставляется с очень простым, но хорошо протестированным исходным кодом .

Попробуйте изменить этот код, заменив тест a[mid] < x с четным / нечетным тестом a[mid] % 2 == 1.

Это должно помочь вам решить проблему, но без нас на самом деле написание кода для вас.

Удачи: -)

Answer 3

Мы знаем критерий, когда работает бинарный поиск. Поскольку массив имеет свойство 000..0111..1, мы можем легко использовать здесь бинарный поиск.

В бинарном поиске есть две границы, скажем, они низкие и высокие, где низкий = первый индекс и высокий = последний индекс массива. И в каждом итераторе мы находим средний элемент от низкого до высокого с помощью (низкий + высокий) / 2. Итак, когда мы находим элемент среднего для проверки, что мы можем сделать здесь? Мы можем проверить, является ли оно четным или нет. Если число нечетное, мы можем игнорировать элементы от низкого до среднего индекса, поскольку все элементы от низкого до среднего индекса будут нечетными. В этом случае мы можем изменить нижний граничный минимум до среднего + 1. Теперь, если индекс среднего уровня четный, тогда этот показатель среднего уровня может быть нашим ответом, но ответ может быть между низким и средним показателями - 1. Таким образом, мы снизим нашу более высокую границу до среднего уровня - 1.

Таким образом, мы можем получить минимальный индекс с четным числом.

код:

ans = len(list)
low = 0, high = len(list) - 1
while low <= high:
    mid = (low + high) // 2
    if list[mid] % 2:
        low = mid + 1
    else:
        ans = mid
        high = mid - 1

# here ans is the index of the first even number

Answer 4

Рэйнер Фернандес понял это правильно в другом ответе: бинарный поиск делает это за O (log n) раз. Это работает потому, что входной список эффективно отсортирован в порядке убывания четность . Поскольку все, что вас волнует, это четность, этого достаточно для бинарного поиска; Ваш вход эквивалентен единице со всеми 0 и 1, что касается бинарного поиска. Вы можете думать об этом как о запуске бинарного поиска с поиском 1/2 и возвращении последнего индекса бинарного поиска до того, как он не смог найти свою цель.

В итоге: проверьте значение в середине списка , Если он четный, вы знаете, что последний нечетный элемент находится слева; в противном случае, если это нечетно, вы знаете, что последний нечетный элемент - это этот элемент или справа от него. Затем повторите эту же процедуру для самого маленького подмассива, в котором вы определили, что существует последний нечетный элемент.