Búsqueda lineal y binaria

Estructuras de datos y algoritmos en Python

Miriam Antona

Software engineer

Algoritmos de búsqueda

Buscar es una operación esencial
- Varias formas
Algoritmos para buscar un elemento en una colección:
- Búsqueda lineal
- Búsqueda binaria

Búsqueda lineal

Recorrer cada elemento

Representación esquemática de una lista de números desordenados.

Elemento encontrado
- el algoritmo se detiene
- devuelve el resultado
Elemento no encontrado
- el algoritmo continúa

Búsqueda lineal

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

Búsqueda lineal: complejidad

Complejidad: $O(n)$

Búsqueda binaria

Solo para listas ordenadas

Representación esquemática de una lista con números ordenados.

¿15 ???

Búsqueda binaria

Solo para listas ordenadas

Representación esquemática de una lista con números ordenados. Hay una variable llamada first que apunta a la primera posición de la lista.

¿15 ???

def binary_search(ordered_list, search_value):
  first = 0

Búsqueda binaria

Solo para listas ordenadas

Representación esquemática de una lista con números ordenados. Hay una variable llamada first que apunta a la primera posición de la lista y otra variable llamada last que apunta a la última posición.

¿15 ???

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


  while first <= last:

Búsqueda binaria

Solo para listas ordenadas

Representación esquemática de una lista con números ordenados. Hay una variable llamada first que apunta a la primera posición, otra llamada last que apunta a la última posición y otra llamada middle que apunta a la posición central.

¿15 ???

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

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

Búsqueda binaria

Solo para listas ordenadas

Representación esquemática de una lista con números ordenados. Hay una variable llamada first que apunta a la primera posición, otra llamada last que apunta a la última y otra llamada middle que apunta a la central. El número 12 está en la posición central y está en amarillo.

¿15 ???
Compara search_value con el elemento del medio de la 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]:

Búsqueda binaria

Solo para listas ordenadas

Representación esquemática de una lista con números ordenados. Hay una variable llamada first que apunta a la primera posición, otra llamada last que apunta a la posición media menos uno, y otra llamada middle que apunta a la posición central. Los elementos entre las posiciones first y middle están en verde.

¿15 ???
Compara search_value con el elemento del medio de la 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

Búsqueda binaria

Solo para listas ordenadas

Representación esquemática de una lista con números ordenados. Hay una variable llamada first que apunta a la primera posición, otra llamada last que apunta a la última, y otra llamada middle que apunta a la central. El número 12 está en la posición central y está en amarillo.

¿15 ???
Compara search_value con el elemento del medio de la 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:

Búsqueda binaria

Solo para listas ordenadas

Representación esquemática de una lista con números ordenados. Hay una variable llamada first que apunta a la posición media más uno, otra llamada last que apunta a la última posición y otra llamada middle que apunta a la posición central. Los elementos entre las posiciones first y middle están en verde.

¿15 ???
Compara search_value con el elemento del medio de la 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

Búsqueda binaria

Solo para listas ordenadas

Representación esquemática de una lista con números ordenados. El puntero middle se ha movido y apunta al elemento entre first y last. Los elementos entre first y middle están en verde.

¿15 ???
Compara search_value con el elemento del medio de la 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

Búsqueda binaria

Solo para listas ordenadas

Representación esquemática de una lista con números ordenados. El puntero middle se ha movido y apunta al elemento entre first y last. Los elementos entre first y middle están en verde. El elemento al que apunta middle, 17, se va a comparar con el número 15.

¿15 ???
Compara search_value con el elemento del medio de la 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

Búsqueda binaria

Solo para listas ordenadas

Representación esquemática de una lista con números ordenados. El puntero last se ha movido y apunta al mismo número que el puntero first.

¿15 ???
Compara search_value con el elemento del medio de la 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

Búsqueda binaria

Solo para listas ordenadas

Representación esquemática de una lista con números ordenados. El puntero middle se ha movido y apunta al mismo número que los punteros first y last.

¿15 ???
Compara search_value con el elemento del medio de la 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

Búsqueda binaria

Solo para listas ordenadas

Representación esquemática de una lista con números ordenados. Los punteros first, last y middle apuntan al mismo número, 15, que se va a comparar con el número 15.

¿15 ???
Compara search_value con el elemento del medio de la 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

Búsqueda binaria

Solo para listas ordenadas

Representación esquemática de una lista con números ordenados. El número 15 está rodeado por un círculo.

¿15 ???
Compara search_value con el elemento del medio de la 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

Búsqueda binaria: complejidad

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

Representación gráfica de la búsqueda lineal y la búsqueda binaria.

¡Vamos a practicar!

Estructuras de datos y algoritmos en Python