объяснение бинарного дерева почему это работает

Question

объяснение бинарного дерева почему это работает

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

class Dictlist(dict):
    def __setitem__(self, key, value):
        try:
            self[key]
        except KeyError:
            super(Dictlist, self).__setitem__(key, [])
        self[key].append(value)

Пример вывода:

>>> d = dictlist.Dictlist()
>>> d['test'] = 1
>>> d['test'] = 2
>>> d['test'] = 3
>>> d
{'test': [1, 2, 3]}
>>> d['other'] = 100
>>> d
{'test': [1, 2, 3], 'other': [100]}

4

python binary-search

задан eyllanesc 17 March 2019 в 20:46

3 ответа

Другие вопросы по тегам:

python binary-search

Похожие вопросы:

score 0 · Answer 1

Вы правы в том, что это неправильно!

Это даст вам правильный результат, но давайте посмотрим, что на самом деле происходит.

  if guess == item:
    return mid
  if guess > item:
    high = mid - 1
  else:
    low = mid + 1

На первой итерации, guess == list[mid] == list[high] == 9. 3 меньше 9, так что высокий будет уменьшаться.

В следующей итерации, снова mid == high, но высокий на 1 меньше.

высокий будет продолжать уменьшаться до guess == list[mid] == list[high] == list[1] == 3

score 0 · Answer 2

Это действительно должно быть (low+high)//2. Как и сейчас, mid начинается с последнего элемента в списке и всегда проходит через остальную часть условия guess>item. Таким образом, high уменьшается на 1 каждый раз, а low никогда не меняется (с нуля). Процесс заканчивается тем, что проходит все элементы от последнего к первому, что вовсе не является двоичным поиском (скорее, последовательным поиском).

score 0 · Answer 3

Это работает, потому что mid всегда находится в правильном диапазоне, но это линейный поиск, а не двоичный. Вы можете проверить это, напечатав изучаемые индексы:

def binary_search(list, item):
    low = 0  
    high = len(list)-1  #sets upper range to length of provided list

    while low <= high:
        mid = (low + high) #why does (low + high) give me middle of list?
        print("mid =", mid)
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1

Ищите -1 в вашем примере:

>>> print (binary_search([1,3,5,7,9],-1))
mid = 4
mid = 3
mid = 2
mid = 1
mid = 0
None

Итак, вы правы: вы должны разделить mid на 2 (и избегайте использования list в качестве имени переменной).