class BinarySearch():

  def search_iterative(self, list, item):
    # в переменных low и high хранятся границы той части списка, в которой выполняется поиск
    low = 0
    high = len(list) - 1

    # Пока эта часть не сократится до одного элемента ...
    while low <= high:
      # ... проверяем средний элемент
      mid = (low + high) // 2
      guess = list[mid]
      # Если значение найдено возвращаем его номер(индекс списка)
      if guess == item:
        return mid
      # Если найдено значение больше - уменьшаем верхний индекс(границу)
      if guess > item:
        high = mid - 1
      # Если найдено значение меньше - увеличиваем нижний индекс(границу)
      else:
        low = mid + 1

    # Элемент не найден
    return None

# Бинарный поиск через рекурсивную функцию
  def search_recursive(self, search_list, low, high, item):
    # Проверка базового варианта
    if high >= low: 
  
        mid = (high + low) // 2
        guess = search_list[mid]
  
        # Если элемент присутствует в самой середине
        if guess == item:
            return mid 
  
        # Если элемент меньше среднего, то он может присутствовать только в левом подмассиве
        elif guess > item: 
            return self.search_recursive(search_list, low, mid - 1, item)
  
        # В противном случае элемент может присутствовать только в правом подмассиве
        else: 
            return self.search_recursive(search_list, mid + 1, high, item)
  
    else: 
        # Элемент отсутствует в массиве
        return None

if __name__ == "__main__":
  # Мы должны инициализировать класс, чтобы использовать методы этого класса
  bs = BinarySearch()
  my_list = [1, 3, 5, 7, 9]
  
  print(bs.search_iterative(my_list, 3)) # => 1

  # "None" в Python означает ничего. Мы используем для обозначения того, что элемент не найден.
  print(bs.search_iterative(my_list, -1)) # => None