Búsquedas binarias

sort ordena la lista creada y sorted ordena una lista en una nueva sin modificar la original

Comparto una imagen donde podrán ver el ejercicio de la clase por pasos:

El método sort ordena la lista con que trabajamos. La built-in function sorted ordena la lista pero retorna una nueva lista ordenada ubicada en un espacio de memoria completamente distinto.

cuando usamos lista.sort() estamos modificando la lista y ordenando sus datos.

mientras que cuando usamos sorted(), nos devuelve la lista ordenada sin modificar la lista original.

"O lo encontramos o dividimos la lista por la mitad"
Busqueda binaria en una lista ordenada de elementos

Libro recomendado: https://link.springer.com/book/10.1007/978-3-319-13072-9

Para entender algoritmos les recomiendo este video de Fredy Vega explicando en 7 minutos!

tengo una libreria con varios metodos de ordenamiento en mi cuenta de github por si les interesa, aun sigo actualizandola con metodos de ordenamiento y metodos de busqueda. Pero esta en C++.

se que estamos en un curso de python pero es realmente facil adaptar la logica empleada, para un codigo de un lenguaje de programacion diferente

https://github.com/josejmv/libreria-1

Paso por paso:

<code>

valores = (2,3,4,5,9,10,14,15,16,19)
####### 0 1 2 3 4  5  6 7  8  9  ### "tienen una longitud de 9"
"BUSCAMOS LA  ' 8 '  POSICIÓN (16)"

# "sumamos los números que están en la mitad de la longitud de la tupla(en este caso)"
4+5= 9
# "dividimos el total entre la mitad (2), solo obtenemos la parte entera del cociente"
9/2 = 4.5 = 4
# "afirmamos que que el numero mayor (16) es mayor que 9 y es TRUE por lo tanto"
(0<x<4] # "todos los números menores detrás de la  posición 4 (inclusivo) son desechados"
# "Sumamos 5 + 9 y lo dividimos entre la mitad (2)"
5+9 = 14
14/2 = 7
# "Luego afirmamos que que el numero mayor (16) es mayor que 15 y es TRUE por lo tanto"
(0<x<7] # "todos los números menores detrás de la  posición 7 (inclusivo) son desechados" 
# "Sumamos 8 + 9, lo dividimos entre la mitad (2) y solo obtenemos la parte entera del cociente"
8+9 = 17 
17/2 = 8
# "y la  posición 8 es 16 = 16"

</code>

sorted(), devuelve una nueva lista ordenada, sin afectar a la lista original.
list.sort() ,ordena la lista en el lugar , mutando los índices de la lista y devuelve None(como todas las operaciones en el lugar).

David tiene un error, al encontrar el punto medio no es 5 + 4 = 9 NO!

Tenemos
2, 3, 4, 5, 9, 10, 14, 15, 16, 19
Sus indices entonces son:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Quedando de la siguiente manera:

[2, 3, 4, 5, 9, 10, 14, 15, 16, 19]
 0, 1, 2, 3, 4,  5 ,  6 ,  7 ,  8 ,  9

Para encontrar el punto medio se toma el indice inicial ACTUAL, se suma con el indice medio FINAL y luego se divide entre dos:
(0 + 9) / 2 = 9 / 2 = 4.5
Aproximando al valor minimo da:
4

Creo que debieron haber preparado mejor esta clase, su falta de orden ocasiono una explicación pobre. Me parece que improviso, lo cual afecto su ejemplo, que se puede ver al inicio de la explicación cuando duda y traga saliva

a=[1,5,3,9,1,0,6]
sorted(a)
[0, 1, 1, 3, 5, 6, 9]
a
[1, 5, 3, 9, 1, 0, 6]
a.sort()
a
[0, 1, 1, 3, 5, 6, 9]

Hasta el momento he entendido todo y sin problemas pero hubiera sido bueno que explicaras punto por punto como se estructuran, igual que paso con el “Zip” que solo lo fue usando de la nada sin ninguna explicación.
¿Podrías ampliar este conocimiento con otro video?

Sort: ordenar lista.
Sorted: crea lista ordenada desde y sin modificar lista original.

como le gusta explicar este tema a David jajaja ya me lo explico tres veces en un solo path de aprendizaje igual me parece cada vez mas excelente

Para reforzar lo aprendido, mirate la clase dada por Facundo del mismo tema y del mismo lenguaje

Otros Algoritmos de búsqueda en Python 🐍

.
✅ Membership Operators
✅ Linear Search
✅ Binary Search
✅ Jump Search
✅ Fibonacci Search
✅ Exponential Search
✅ Interpolation Search

Este gif lo ejemplifica perfecta. Arriba la búsqueda binaria y abajo la fuerza bruta.

El algoritmo que explica es hermoso, si no lo entendieron desafortunadamente tendrán que buscar en fuentes externas ya que es de gran utilidad en la ciencia de datos

Si alguien batalló con este algoritmo, aunque ya hay gente que dio vídeos aquí les doy un ejemplo rápido y común en programación:

El juego del numero mágico, en el que tienes que escoger un numero del 1 al 100. La mejor manera de acertar en este juego es con la misma búsqueda binaria, intentando dividir constantemente tu rango de búsqueda a la mitad, un ejemplo:

numero_magico = 31

primer intento: 50

respuesta: “el numero es menor”

segundo intento: 25

respuesta: “el numero es mayor”

tercer intento: 37

respuesta: “el numero es menor”

cuarto intento: 31

respuesta: “acertaste”

como se pueden dar cuenta, redujimos lo que en el algoritmo de iteracion/“brute force” serian 31 pasos, a únicamente 4, ese es el principio de este algoritmo: reduce tu trabajo lo mínimo posible, que en este caso, seria a la mitad debido a cuestiones de azar.

Diferencia entre sort y sorted. 🔛

La diferencia radica en que el método sort ordena la lista y reasigna esa nueva lista ordenada en la misma variable.

En cambio si utilizamos la función sorted() sobre la lista. Solo ordena, pero no lo guarda en la misma variable. Se tendría que asignar a la misma o a otra variable.

>>> lista = [2,6,5,3,1,0,-1,100,99] 
>>> sorted(lista) 
[-1, 0, 1, 2, 3, 5, 6, 99, 100] 
>>> lista 
[2, 6, 5, 3, 1, 0, -1, 100, 99] 
>>> lista.sort() >>> lista 
[-1, 0, 1, 2, 3, 5, 6, 99, 100] >>>

Explicación en código usando .sort() y sorted()

el concepto es sencillo de binary Search pues es solo para ordenados.

¿Existe alguna manera de implementar este algoritmo en listas con texto?

De acuerdo a lo enseñado, se puede resumir que sort (ordena la lista creada) y sorted ordena una lista ya creada en una lista nueva, sin modificar la original.

La función sort (): Modificará la lista a la que se llama.
La función sorted (): Creará una nueva lista que contiene una versión ordenada de la lista que se proporciona.

Implementación de binary search

Les comparto mi implementación de binary search.

Código

from typing import List

def binary_search(target: int, source: List[int]) -> bool:
    """Checks if a number is in the provided list.
    
    Time Complexity: O(log n)

    Returns:
        bool: Returns True if the number is in the provided list. Otherwise, it returns False.
    """

    length = len(source)
    if length == 0:
        return False

    middle = length // 2


    if length == 1:
        return source[0] == target
    
    if length == 2:
        return source[0] == target or source[1] == target
    
    if source[middle] == target:
        return True

    if source[middle] > target:
        return binary_search(target, source[:middle])

    return binary_search(target, source[middle:])


if __name__ == '__main__':
    import unittest
    from typing import Tuple

    from ddt import ddt  # type: ignore
    from ddt import unpack  # type: ignore
    from ddt import data  # type: ignore


    @ddt
    class BinarySearchTestCaseç(unittest.TestCase):

        @data(
            ((1, [1, 2, 3, 4]), True),
            ((2, [1, 2, 3, 4]), True),
            ((3, [1, 2, 3, 4]), True),
            ((4, [1, 2, 3, 4]), True),
            ((5, [1, 2, 3, 4]), False),
            ((6, [1, 2, 3, 4]), False),
            ((7, [1, 2, 3, 4]), False),
        )
        @unpack
        def test_binary_search(self, args: Tuple[int, List[int]], expected_result: bool):
            result = binary_search(*args)
            self.assertEqual(result, expected_result)

    unittest.main(verbosity=2)

def busqueda_binaria(lista, comienzo, final, objetivo):
    print(f'buscando {objetivo} entre el {lista[comienzo]} y {lista[final - 1]}')
    if comienzo > final:
        return False

    medio = (comienzo + final) //2

    if lista[medio] == objetivo:
        return True
    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, medio + 1, final, objetivo)
    else:
        return busqueda_binaria(lista, comienzo, medio -1, objetivo)

Sort: ordena la lista actual y la cambia.
Sorted: ordena pero no cambia el valor de la lista actual.

Aquí lo explican mejor.

https://www.youtube.com/watch?v=6-e_kVZkECI

Para los que no entendieron de primeras (como yo xd) aquí un enlace.

Los algoritmos de ordenamiento como olvidar los dolores de cabeza que causaron.

Genial!! Me encantó esta clase!

Paso por paso:

<code>

valores = (2,3,4,5,9,10,14,15,16,19)
####### 0 1 2 3 4  5  6 7  8  9  ### "tienen una longitud de 9"
"BUSCAMOS LA  ' 8 '  POSICIÓN (16)"

# "sumamos los números que están en la mitad de la longitud de la tupla(en este caso)"
4+5= 9
# "dividimos el total entre la mitad (2), solo obtenemos la parte entera del cociente"
9/2 = 4.5 = 4
# "afirmamos que que el numero mayor (16) es mayor que 9 y es TRUE por lo tanto"
(0<x<4] # "todos los números menores detrás de la  posición 4 (inclusivo) son desechados"
# "Sumamos 5 + 9 y lo dividimos entre la mitad (2)"
5+9 = 14
14/2 = 7
# "Luego afirmamos que que el numero mayor (16) es mayor que 15 y es TRUE por lo tanto"
(0<x<7] # "todos los números menores detrás de la  posición 7 (inclusivo) son desechados" 
# "Sumamos 8 + 9, lo dividimos entre la mitad (2) y solo obtenemos la parte entera del cociente"
8+9 = 17 
17/2 = 8
# "y la  posición 8 es 16 = 16"

</code>

interesante algoritmo

Clásica explicación con diagramas de flujo y C.

Muy interesante!!!

Genial, la forma de ahorrar procesos de ejecución!

Direferencia:

Con list.sort() Ordenamos y cambiamos dicha lista
Con sorted(list) Ordenamos pero no cambiamos la lista inical

Busqueda binaria:

• Divide y conquista: Cada vez vamos a haciendo el problema mas pequeño descartando pasos inncesarios para aproximarnos a la solucion.
  
• El probblema se divide en 2 en cada iteracion
  
• Cual es el peor caso
  

Ejemplo grafico:

IMPORTANTE Para aplicar este algoritmo se asume que la lista o estructura de datos debe estar ordenada. Si tu lista no esta ordenada y vas a utilizar este algoritmo una sola vez puedes utilizar busqueda sencuencial pero si vas a hacer este tipo de busquedas constantemente vale la pena aplicar un algoritmo de ordenamiento para mejorar el rendimiento del algoritmo

sorted(): La funcion devuele una lista ordenada del objeto iterable que reciba. Se puede especificar el orden ascendente o desendente. Las cadenas de caracteres son ordenadas alfabeticamente y los numeros ya sea de mayor a menor o menor a mayor.

Syntax: sorted(iterable, key = key, reverse = reverse)

un resumen sabroso

number_random = []

for i in range(20):
	number_random.append(random.randint(1, 100))

>>> number_random
[88, 7, 82, 28, 12, 39, 92, 82, 9, 86, 26, 57, 49, 3, 13, 44, 85, 48, 90, 59]


number_random.sort()
>>> number_random
[3, 7, 9, 12, 13, 26, 28, 39, 44, 48, 49, 57, 59, 82, 82, 85, 86, 88, 90, 92]

• La búsqueda binaria, busca en una lista ordenada, empezando por la mitad y descartando la mitad que no contiene o que sea mayor, al elemento buscado.

En qué se fundamenta que funcione el algoritmo de búsqueda binaria?
Se demuestra que para a,b
tal que 0<=a<=b
Se cumple
a <= (a+b)/2 <= b **********
Siempre se encontrará un candidato
A menos que deje de cumplirse la condición inicial

Me gusto mucho esta clase, aprendi muchas cosas nuevas. Gracias