Busca linear e busca binária

Estruturas de Dados e Algoritmos em Python

Miriam Antona

Software engineer

Algoritmos de busca

  • Busca é uma operação essencial
    • Várias formas
  • Algoritmos que procuram um elemento em uma coleção:
    • Busca linear
    • Busca binária
Estruturas de Dados e Algoritmos em Python

Busca linear

  • Percorre cada elemento

Representação esquemática de uma lista de números desordenados.

  • Elemento encontrado
    • algoritmo para
    • retorna o resultado
  • Elemento não encontrado
    • algoritmo continua
Estruturas de Dados e Algoritmos em Python

Busca linear

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
Estruturas de Dados e Algoritmos em Python

Busca linear - complexidade

  • Complexidade: $O(n)$
Estruturas de Dados e Algoritmos em Python

Busca binária

  • Só vale para listas ordenadas

Representação esquemática de uma lista com números ordenados.

  • 15 ???
Estruturas de Dados e Algoritmos em Python

Busca binária

  • Só vale para listas ordenadas

Representação esquemática de uma lista com números ordenados. Há uma variável chamada first que aponta para a primeira posição da lista.

  • 15 ???
def binary_search(ordered_list, search_value):
  first = 0
Estruturas de Dados e Algoritmos em Python

Busca binária

  • Só vale para listas ordenadas

Representação esquemática de uma lista com números ordenados. Há uma variável chamada first que aponta para a primeira posição da lista e outra chamada last que aponta para a última posição.

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


  while first <= last:
Estruturas de Dados e Algoritmos em Python

Busca binária

  • Só vale para listas ordenadas

Representação esquemática de uma lista com números ordenados. Há uma variável chamada first que aponta para a primeira posição da lista, outra chamada last que aponta para a última posição e outra chamada middle que aponta para a posição do meio.

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

  while first <= last:
    middle = (first + last)//2
Estruturas de Dados e Algoritmos em Python

Busca binária

  • Só vale para listas ordenadas

Representação esquemática de uma lista com números ordenados. Há uma variável chamada first que aponta para a primeira posição da lista, outra chamada last que aponta para a última posição e outra chamada middle que aponta para a posição do meio. O número 12 está no meio e está em amarelo.

  • 15 ???
  • Compare search_value com o item do meio da lista
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]:
Estruturas de Dados e Algoritmos em Python

Busca binária

  • Só vale para listas ordenadas

Representação esquemática de uma lista com números ordenados. Há uma variável chamada first que aponta para a primeira posição da lista, outra chamada last que aponta para a posição do meio menos um e outra chamada middle que aponta para a posição do meio. Os elementos entre first e middle estão em verde.

  • 15 ???
  • Compare search_value com o item do meio da lista
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
Estruturas de Dados e Algoritmos em Python

Busca binária

  • Só vale para listas ordenadas

Representação esquemática de uma lista com números ordenados. Há uma variável chamada first que aponta para a primeira posição da lista, outra chamada last que aponta para a última posição e outra chamada middle que aponta para a posição do meio. O número 12 está no meio e está em amarelo.

  • 15 ???
  • Compare search_value com o item do meio da lista
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:
Estruturas de Dados e Algoritmos em Python

Busca binária

  • Só vale para listas ordenadas

Representação esquemática de uma lista com números ordenados. Há uma variável chamada first que aponta para a posição do meio mais um, outra chamada last que aponta para a última posição e outra chamada middle que aponta para a posição do meio. Os elementos entre first e middle estão em verde.

  • 15 ???
  • Compare search_value com o item do meio da lista
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
Estruturas de Dados e Algoritmos em Python

Busca binária

  • Só vale para listas ordenadas

Representação esquemática de uma lista com números ordenados. O ponteiro middle se moveu e aponta para o elemento entre first e last. Os elementos entre first e middle estão em verde.

  • 15 ???
  • Compare search_value com o item do meio da lista
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
Estruturas de Dados e Algoritmos em Python

Busca binária

  • Só vale para listas ordenadas

Representação esquemática de uma lista com números ordenados. O ponteiro middle se moveu e aponta para o elemento entre first e last. Os elementos entre first e middle estão em verde. O elemento apontado por middle, 17, será comparado com o número 15.

  • 15 ???
  • Compare search_value com o item do meio da lista
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
Estruturas de Dados e Algoritmos em Python

Busca binária

  • Só vale para listas ordenadas

Representação esquemática de uma lista com números ordenados. O ponteiro last foi movido e aponta para o mesmo número que o ponteiro first.

  • 15 ???
  • Compare search_value com o item do meio da lista
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
Estruturas de Dados e Algoritmos em Python

Busca binária

  • Só vale para listas ordenadas

Representação esquemática de uma lista com números ordenados. O ponteiro middle foi movido e aponta para o mesmo número que os ponteiros first e last.

  • 15 ???
  • Compare search_value com o item do meio da lista
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
Estruturas de Dados e Algoritmos em Python

Busca binária

  • Só vale para listas ordenadas

Representação esquemática de uma lista com números ordenados. Os ponteiros first, last e middle apontam para o mesmo número, 15, que será comparado com o número 15.

  • 15 ???
  • Compare search_value com o item do meio da lista
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
Estruturas de Dados e Algoritmos em Python

Busca binária

  • Só vale para listas ordenadas

Representação esquemática de uma lista com números ordenados. O número 15 está circulado.

  • 15 ???
  • Compare search_value com o item do meio da lista
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
Estruturas de Dados e Algoritmos em Python

Busca binária - complexidade

  • Complexidade: $O(\log{}n)$

Representação gráfica da busca linear e da busca binária.

Estruturas de Dados e Algoritmos em Python

Vamos praticar!

Estruturas de Dados e Algoritmos em Python

Preparing Video For Download...