Căutare liniară și căutare binară

Structuri de date și algoritmi în Python

Miriam Antona

Software engineer

Algoritmi de căutare

Căutarea este o operație esențială
- Mai multe metode
Algoritmi care caută un element într-o colecție:
- Căutare liniară
- Căutare binară

Căutare liniară

Parcurgerea fiecărui element

Reprezentare schematică a unei liste de numere neordonate.

Element găsit
- algoritmul se oprește
- returnează rezultatul
Element negăsit
- algoritmul continuă

Căutare liniară

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

Căutare liniară - complexitate

Complexitate: $O(n)$

Căutare binară

Se aplică doar listelor ordonate

Reprezentare schematică a unei liste cu numere ordonate.

15 ???

Căutare binară

Se aplică doar listelor ordonate

Reprezentare schematică a unei liste cu numere ordonate. Există o variabilă numită first care indică prima poziție din listă.

15 ???

def binary_search(ordered_list, search_value):
  first = 0

Căutare binară

Se aplică doar listelor ordonate

Reprezentare schematică a unei liste cu numere ordonate. Există o variabilă numită first care indică prima poziție și o variabilă numită last care indică ultima poziție.

15 ???

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


  while first <= last:

Căutare binară

Se aplică doar listelor ordonate

Reprezentare schematică a unei liste cu numere ordonate. Există o variabilă numită first care indică prima poziție, una numită last care indică ultima poziție și una numită middle care indică poziția de mijloc.

15 ???

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

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

Căutare binară

Se aplică doar listelor ordonate

Reprezentare schematică a unei liste cu numere ordonate. Există variabilele first, last și middle. Numărul 12 se află la poziția de mijloc și este colorat în galben.

15 ???
Se compară search_value cu elementul din mijlocul listei

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

Căutare binară

Se aplică doar listelor ordonate

Reprezentare schematică a unei liste cu numere ordonate. Variabila last indică acum poziția de mijloc minus unu. Elementele dintre first și middle sunt colorate în verde.

15 ???
Se compară search_value cu elementul din mijlocul listei

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

Căutare binară

Se aplică doar listelor ordonate

Reprezentare schematică a unei liste cu numere ordonate. Există variabilele first, last și middle. Numărul 12 se află la poziția de mijloc și este colorat în galben.

15 ???
Se compară search_value cu elementul din mijlocul listei

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:

Căutare binară

Se aplică doar listelor ordonate

Reprezentare schematică a unei liste cu numere ordonate. Variabila first indică acum poziția de mijloc plus unu. Elementele dintre first și middle sunt colorate în verde.

15 ???
Se compară search_value cu elementul din mijlocul listei

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

Căutare binară

Se aplică doar listelor ordonate

Reprezentare schematică a unei liste cu numere ordonate. Pointerul middle s-a deplasat și indică elementul dintre first și last. Elementele dintre first și middle sunt colorate în verde.

15 ???
Se compară search_value cu elementul din mijlocul listei

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

Căutare binară

Se aplică doar listelor ordonate

Reprezentare schematică a unei liste cu numere ordonate. Pointerul middle s-a deplasat și indică elementul dintre first și last. Elementele dintre first și middle sunt colorate în verde. Elementul indicat de middle, 17, va fi comparat cu numărul 15.

15 ???
Se compară search_value cu elementul din mijlocul listei

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

Căutare binară

Se aplică doar listelor ordonate

Reprezentare schematică a unei liste cu numere ordonate. Pointerul last s-a deplasat și indică același număr ca pointerul first.

15 ???
Se compară search_value cu elementul din mijlocul listei

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

Căutare binară

Se aplică doar listelor ordonate

Reprezentare schematică a unei liste cu numere ordonate. Pointerul middle s-a deplasat și indică același număr ca pointerii first și last.

15 ???
Se compară search_value cu elementul din mijlocul listei

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

Căutare binară

Se aplică doar listelor ordonate

Reprezentare schematică a unei liste cu numere ordonate. Pointerii first, last și middle indică același număr, 15, care va fi comparat cu numărul 15.

15 ???
Se compară search_value cu elementul din mijlocul listei

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

Căutare binară

Se aplică doar listelor ordonate

Reprezentare schematică a unei liste cu numere ordonate. Numărul 15 este încercuit.

15 ???
Se compară search_value cu elementul din mijlocul listei

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

Căutare binară - complexitate

Complexitate: $O(\log{}n)$

Reprezentare grafică a căutării liniare și binare.

Să exersăm!

Structuri de date și algoritmi în Python