Написал алгоритмы двоичного поиска для Python, как рекурсивную, так и итеративную версии. Как бы вы оценили их эффективность? - PullRequest
Новая
       59

Написал алгоритмы двоичного поиска для Python, как рекурсивную, так и итеративную версии. Как бы вы оценили их эффективность?

0 голосов
/ 10 июля 2020

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

Мне нужны функции для чисто академических c / тестирование для сравнения скоростей с другими тестируемыми мною функциями, включая Python встроенные isinstance () и в методы / операнды.

Я просматриваю строку, содержащую цифры и буквы, и проверяю, является ли символ из нее целым числом.

Таким образом, применение следующих алгоритмов на каждой итерации (т. Е. Символа) l oop в строке выглядит следующим образом:

binSearch("0123456789", "4", 0, 10)

«4» - это просто пример, как вы можете сказать.

binSearch2("0123456789", "w")

«w» - это просто пример, который вы можете сказать.

ПРИМЕЧАНИЕ: Мне известно о существовании модуля bisect. Впрочем, цель и цель моих экспериментов и упражнений не в этом.

# РЕКУРСИВНАЯ ВЕРСИЯ НИЖЕ 

def binSearch(list, digit, low, up):

mid = (low + up) // 2
midd = list[mid]

if digit == midd:
    return True
elif digit > midd:
    if mid == 9: return False
    return True and binSearch(list, digit, mid, up)
elif digit < midd:
    return True and binSearch(list, digit, low, mid)

# ИТЕРАЦИОННАЯ ВЕРСИЯ НИЖЕ 

def binSearch2(list, digit):

low = 0
up = len(list)
mid = (low + up) // 2

while mid > 0:

    if digit == list[mid]: 
        return True

    elif digit > list[mid]:
        low = mid
        if low == 9: break

    else:
        up = mid

    mid = (low + up) // 2
    #print(low, mid, up)

if digit == list[mid]: return True

return False

Комментарии приветствуются!

1 Ответ

1 голос
/ 10 июля 2020

Обе ваши функции можно улучшить, убедившись, что mid исключен из диапазона индексов, который вы учитываете на следующем проходе (либо рекурсивный вызов, либо последующий l oop). Поскольку вы только что проверили, имеет ли индекс mid нужное вам значение (а это не так), вы можете исключить mid из верхнего интервала, установив low на mid+1 на следующем проходе. Он уже исключен из нижних интервалов, так как индекс up находится за пределами конца интервала (он наполовину открыт).

Вы также жестко запрограммировали странный базовый случай отказа в функцию , где вы проверяете наличие mid==9. Это не будет работать должным образом для большого количества входных данных (например, более коротких строк) и может привести к тому, что ваш код будет работать вечно или вызвать исключения в зависимости от того, где символ иглы относительно символов в строке стога сена (попробуйте найти ' ' с вашим текущим кодом). Правильный тест для базового случая - low >= up, что означает, что ваш интервал поиска пуст. Для итеративного кода вы будете продолжать цикл до тех пор, пока low < up.

Вот как я бы обновил ваши функции: 

def binSearch(list, digit, low, up):
    if low >= up:        # base case moved here, tested properly
        return False
    mid = (low + up) // 2
    midd = list[mid]
    if digit == midd:
        return True
    elif digit > midd:   # no more base case code in this block
        return binSearch(list, digit, mid+1, up)   # exclude mid from the next interval
    elif digit < midd:
        return binSearch(list, digit, low, mid)


def binSearch2(list, digit):
    low = 0
    up = len(list)
    while low < up:  # base case test is here now
        mid = (low + up) // 2  # move this here, so we don't need to repeat it
        if digit == list[mid]: 
            return True
        elif digit > list[mid]:
            low = mid + 1      # skip mid when moving up, no longer test base case here
        else:
            up = mid
    return False
...