Линейный и бинарный поиск

Структуры данных и алгоритмы на Python

Miriam Antona

Software engineer

Алгоритмы поиска

Поиск — важная операция
- Несколько способов
Алгоритмы поиска элемента в коллекции:
- Линейный поиск
- Бинарный поиск

Линейный поиск

Перебор каждого элемента

Схематичное представление списка неупорядоченных чисел.

Элемент найден
- алгоритм останавливается
- возвращает результат
Элемент не найден
- алгоритм продолжает работу

Линейный поиск

def linear_search(unordered_list, search_value):

  for index in range(len(unordered_list)):

    if unordered_list[index] == search_value:

      return True

  return False

print(linear_search([15,2,21,3,12,7,8], 8))

True

print(linear_search([15,2,21,3,12,7,8], 800))

False

Линейный поиск — сложность

Сложность: $O(n)$

Бинарный поиск

Применяется только к упорядоченным спискам

Схематичное представление списка упорядоченных чисел.

15 ???

Бинарный поиск

Применяется только к упорядоченным спискам

Схематичное представление списка упорядоченных чисел. Переменная first указывает на первую позицию списка.

15 ???

def binary_search(ordered_list, search_value):
  first = 0

Бинарный поиск

Применяется только к упорядоченным спискам

Схематичное представление списка упорядоченных чисел. Переменная first указывает на первую позицию списка, переменная last — на последнюю.

15 ???

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1


  while first <= last:

Бинарный поиск

Применяется только к упорядоченным спискам

Схематичное представление списка упорядоченных чисел. Переменная first указывает на первую позицию, last — на последнюю, middle — на среднюю.

15 ???

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2

Бинарный поиск

Применяется только к упорядоченным спискам

Схематичное представление списка упорядоченных чисел. Переменная first указывает на первую позицию, last — на последнюю, middle — на среднюю. Число 12 стоит на средней позиции и выделено жёлтым.

15 ???
Сравниваем search_value с элементом в середине списка

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2

    if search_value == ordered_list[middle]:

      return True

    elif search_value < ordered_list[middle]:

Бинарный поиск

Применяется только к упорядоченным спискам

Схематичное представление списка упорядоченных чисел. Переменная first указывает на первую позицию, last — на позицию middle минус один, middle — на среднюю. Элементы между first и middle выделены зелёным.

15 ???
Сравниваем search_value с элементом в середине списка

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1

Бинарный поиск

Применяется только к упорядоченным спискам

15 ???
Сравниваем search_value с элементом в середине списка

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:

Бинарный поиск

Применяется только к упорядоченным спискам

Схематичное представление списка упорядоченных чисел. Переменная first указывает на позицию middle плюс один, last — на последнюю позицию, middle — на среднюю. Элементы между first и middle выделены зелёным.

15 ???
Сравниваем search_value с элементом в середине списка

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Бинарный поиск

Применяется только к упорядоченным спискам

Схематичное представление списка упорядоченных чисел. Указатель middle сдвинулся и указывает на элемент между first и last. Элементы между first и middle выделены зелёным.

15 ???
Сравниваем search_value с элементом в середине списка

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Бинарный поиск

Применяется только к упорядоченным спискам

Схематичное представление списка упорядоченных чисел. Указатель middle сдвинулся и указывает на элемент между first и last. Элементы между first и middle выделены зелёным. Элемент, на который указывает middle — число 17 — сравнивается с числом 15.

15 ???
Сравниваем search_value с элементом в середине списка

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Бинарный поиск

Применяется только к упорядоченным спискам

Схематичное представление списка упорядоченных чисел. Указатель last сдвинулся и указывает на то же число, что и first.

15 ???
Сравниваем search_value с элементом в середине списка

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Бинарный поиск

Применяется только к упорядоченным спискам

Схематичное представление списка упорядоченных чисел. Указатель middle сдвинулся и указывает на то же число, что и first и last.

15 ???
Сравниваем search_value с элементом в середине списка

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Бинарный поиск

Применяется только к упорядоченным спискам

Схематичное представление списка упорядоченных чисел. Указатели first, last и middle указывают на одно число — 15, которое сравнивается с числом 15.

15 ???
Сравниваем search_value с элементом в середине списка

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Бинарный поиск

Применяется только к упорядоченным спискам

Схематичное представление списка упорядоченных чисел. Число 15 обведено кружком.

15 ???
Сравниваем search_value с элементом в середине списка

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

  return False

Бинарный поиск — сложность

Сложность: $O(\log{}n)$

Графическое сравнение линейного и бинарного поиска.

Давайте потренируемся!

Структуры данных и алгоритмы на Python