Lineární a binární vyhledávání

Datové struktury a algoritmy v Pythonu

Miriam Antona

Software engineer

Vyhledávací algoritmy

Vyhledávání je základní operace
- Několik způsobů
Algoritmy pro vyhledávání prvku v kolekci:
- Lineární vyhledávání
- Binární vyhledávání

Lineární vyhledávání

Prochází každý prvek

Schematické znázornění seznamu neseřazených čísel.

Prvek nalezen
- algoritmus se zastaví
- vrátí výsledek
Prvek nenalezen
- algoritmus pokračuje

Lineární vyhledávání

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

Lineární vyhledávání – složitost

Složitost: $O(n)$

Binární vyhledávání

Platí pouze pro seřazené seznamy

Schematické znázornění seznamu seřazených čísel.

15 ???

Binární vyhledávání

Platí pouze pro seřazené seznamy

Schematické znázornění seznamu seřazených čísel. Proměnná first ukazuje na první pozici seznamu.

15 ???

def binary_search(ordered_list, search_value):
  first = 0

Binární vyhledávání

Platí pouze pro seřazené seznamy

Schematické znázornění seznamu seřazených čísel. Proměnná first ukazuje na první pozici, proměnná last na poslední pozici seznamu.

15 ???

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


  while first <= last:

Binární vyhledávání

Platí pouze pro seřazené seznamy

Schematické znázornění seznamu seřazených čísel. Proměnná first ukazuje na první pozici, last na poslední pozici a middle na střední pozici seznamu.

15 ???

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

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

Binární vyhledávání

Platí pouze pro seřazené seznamy

Schematické znázornění seznamu seřazených čísel. Proměnná first ukazuje na první pozici, last na poslední a middle na střední pozici. Číslo 12 na střední pozici je zvýrazněno žlutě.

15 ???
Porovnat search_value s prvkem uprostřed (middle) seznamu

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]:

Binární vyhledávání

Platí pouze pro seřazené seznamy

Schematické znázornění seznamu seřazených čísel. Proměnná first ukazuje na první pozici, last na pozici před středem a middle na střední pozici. Prvky mezi first a middle jsou zvýrazněny zeleně.

15 ???
Porovnat search_value s prvkem uprostřed (middle) seznamu

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

Binární vyhledávání

Platí pouze pro seřazené seznamy

15 ???
Porovnat search_value s prvkem uprostřed (middle) seznamu

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:

Binární vyhledávání

Platí pouze pro seřazené seznamy

Schematické znázornění seznamu seřazených čísel. Proměnná first ukazuje na pozici za středem, last na poslední a middle na střední pozici. Prvky mezi first a middle jsou zvýrazněny zeleně.

15 ???
Porovnat search_value s prvkem uprostřed (middle) seznamu

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

Binární vyhledávání

Platí pouze pro seřazené seznamy

Schematické znázornění seznamu seřazených čísel. Ukazatel middle se přesunul na prvek mezi first a last. Prvky mezi first a middle jsou zvýrazněny zeleně.

15 ???
Porovnat search_value s prvkem uprostřed (middle) seznamu

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

Binární vyhledávání

Platí pouze pro seřazené seznamy

Schematické znázornění seznamu seřazených čísel. Ukazatel middle se přesunul na prvek mezi first a last. Prvky mezi first a middle jsou zvýrazněny zeleně. Prvek, na který middle ukazuje (17), je porovnáván s číslem 15.

15 ???
Porovnat search_value s prvkem uprostřed (middle) seznamu

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

Binární vyhledávání

Platí pouze pro seřazené seznamy

Schematické znázornění seznamu seřazených čísel. Ukazatel last se přesunul na stejný prvek jako ukazatel first.

15 ???
Porovnat search_value s prvkem uprostřed (middle) seznamu

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

Binární vyhledávání

Platí pouze pro seřazené seznamy

Schematické znázornění seznamu seřazených čísel. Ukazatel middle se přesunul na stejný prvek jako first a last.

15 ???
Porovnat search_value s prvkem uprostřed (middle) seznamu

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

Binární vyhledávání

Platí pouze pro seřazené seznamy

Schematické znázornění seznamu seřazených čísel. Ukazatele first, last a middle ukazují na stejný prvek, číslo 15, které je porovnáváno s číslem 15.

15 ???
Porovnat search_value s prvkem uprostřed (middle) seznamu

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

Binární vyhledávání

Platí pouze pro seřazené seznamy

Schematické znázornění seznamu seřazených čísel. Číslo 15 je zakroužkováno.

15 ???
Porovnat search_value s prvkem uprostřed (middle) seznamu

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

Binární vyhledávání – složitost

Složitost: $O(\log{}n)$

Grafické znázornění lineárního a binárního vyhledávání.

Lass uns üben!

Datové struktury a algoritmy v Pythonu