Wyszukiwanie liniowe i binarne

Struktury danych i algorytmy w Pythonie

Miriam Antona

Software engineer

Algorytmy wyszukiwania

Wyszukiwanie to podstawowa operacja
- Kilka sposobów
Algorytmy wyszukujące element w kolekcji:
- Wyszukiwanie liniowe
- Wyszukiwanie binarne

Wyszukiwanie liniowe

Przechodzenie przez każdy element

Schematyczne przedstawienie listy nieuporządkowanych liczb.

Element znaleziony
- algorytm zatrzymuje się
- zwraca wynik
Element nieznaleziony
- algorytm kontynuuje

Wyszukiwanie liniowe

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

Wyszukiwanie liniowe – złożoność

Złożoność: $O(n)$

Wyszukiwanie binarne

Dotyczy tylko list uporządkowanych

Schematyczne przedstawienie listy zawierającej liczby w kolejności.

15 ???

Wyszukiwanie binarne

Dotyczy tylko list uporządkowanych

Schematyczne przedstawienie listy zawierającej liczby w kolejności. Zmienna first wskazuje na pierwszą pozycję listy.

15 ???

def binary_search(ordered_list, search_value):
  first = 0

Wyszukiwanie binarne

Dotyczy tylko list uporządkowanych

Schematyczne przedstawienie listy zawierającej liczby w kolejności. Zmienna first wskazuje na pierwszą pozycję listy, a zmienna last na ostatnią.

15 ???

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


  while first <= last:

Wyszukiwanie binarne

Dotyczy tylko list uporządkowanych

Schematyczne przedstawienie listy zawierającej liczby w kolejności. Zmienna first wskazuje na pierwszą pozycję, last na ostatnią, a middle na środkową.

15 ???

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

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

Wyszukiwanie binarne

Dotyczy tylko list uporządkowanych

Schematyczne przedstawienie listy zawierającej liczby w kolejności. Zmienne first, last i middle wskazują odpowiednio na pierwszą, ostatnią i środkową pozycję. Liczba 12 na środkowej pozycji jest zaznaczona na żółto.

15 ???
Porównaj search_value z elementem w środku listy

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

Wyszukiwanie binarne

Dotyczy tylko list uporządkowanych

Schematyczne przedstawienie listy zawierającej liczby w kolejności. Zmienna first wskazuje na pierwszą pozycję, last na pozycję środkową minus jeden, a middle na środkową. Elementy między first a middle są zaznaczone na zielono.

15 ???
Porównaj search_value z elementem w środku listy

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

Wyszukiwanie binarne

Dotyczy tylko list uporządkowanych

15 ???
Porównaj search_value z elementem w środku listy

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:

Wyszukiwanie binarne

Dotyczy tylko list uporządkowanych

Schematyczne przedstawienie listy zawierającej liczby w kolejności. Zmienna first wskazuje na pozycję środkową plus jeden, last na ostatnią, a middle na środkową. Elementy między first a middle są zaznaczone na zielono.

15 ???
Porównaj search_value z elementem w środku listy

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

Wyszukiwanie binarne

Dotyczy tylko list uporządkowanych

Schematyczne przedstawienie listy zawierającej liczby w kolejności. Wskaźnik middle przesunął się i wskazuje na element między first a last. Elementy między first a middle są zaznaczone na zielono.

15 ???
Porównaj search_value z elementem w środku listy

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

Wyszukiwanie binarne

Dotyczy tylko list uporządkowanych

15 ???
Porównaj search_value z elementem w środku listy

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

Wyszukiwanie binarne

Dotyczy tylko list uporządkowanych

Schematyczne przedstawienie listy zawierającej liczby w kolejności. Wskaźnik last przesunął się i wskazuje na tę samą liczbę co wskaźnik first.

15 ???
Porównaj search_value z elementem w środku listy

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

Wyszukiwanie binarne

Dotyczy tylko list uporządkowanych

Schematyczne przedstawienie listy zawierającej liczby w kolejności. Wskaźnik middle przesunął się i wskazuje na tę samą liczbę co wskaźniki first i last.

15 ???
Porównaj search_value z elementem w środku listy

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

Wyszukiwanie binarne

Dotyczy tylko list uporządkowanych

Schematyczne przedstawienie listy zawierającej liczby w kolejności. Wskaźniki first, last i middle wskazują na tę samą liczbę, 15, która jest porównywana z liczbą 15.

15 ???
Porównaj search_value z elementem w środku listy

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

Wyszukiwanie binarne

Dotyczy tylko list uporządkowanych

Schematyczne przedstawienie listy zawierającej liczby w kolejności. Liczba 15 jest zaznaczona kółkiem.

15 ???
Porównaj search_value z elementem w środku listy

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

Wyszukiwanie binarne – złożoność

Złożoność: $O(\log{}n)$

Graficzne porównanie wyszukiwania liniowego i binarnego.

Czas na ćwiczenia!

Struktury danych i algorytmy w Pythonie