El ALGORITMO de Búsqueda que todo desarrollador DEBERÍA CONOCER
Vložit
- čas přidán 5. 08. 2024
- 👉🏻 Obtén 7 días de trial y 25$ de crédito en UpCloud
👉🏻 upcloud.com/signup/?promo=bet...
La BUSQUEDA BINARIA es uno de los algoritmos más eficientes para realizar búsquedas rápidas en vectores y arrays... Aprende como usarlo!
👾 Redes sociales 👾
► Twitter: / bettatech
► Instagram: / betta_tech
► Canal Secundario: / @forkdebettatech
► Slack: bit.ly/33gaDDM
👨🏼🏫 MIS CURSOS 👨🏼🏫
👽 Curso de iniciación a la programación con JavaScript:
► bit.ly/3kr4bTc
👕 MERCHANDISING DEL CANAL:
► Tienda CZcams: / bettatech
► Tienda Teespring: teespring.com/stores/bettatec...
⭐️ AFILIADOS ⭐️
🎁 7% Descuento en HOSTINGER (Código BETTATECH)
► www.hostg.xyz/aff_c?offer_id=...
🧠 Autocompletado con IA (Kite)
► www.kite.com/get-kite/?...
🐾 MacPaw (CleanMyMacX):
► macpaw.audw.net/c/2523912/941...
🎵 TODA la música es de EpidemicSound:
► www.epidemicsound.com/referra...
✉️ CONTACTO PROFESIONAL:
► Respuesta no garantizada:
bettatechyt@gmail.com
📚 LIBROS 📚
Design Patterns
► amzn.to/39XuQlq
Head First Design Patterns
► amzn.to/2uq6XUq
Refactoring
► amzn.to/2SQnf2c
Clean Architecture
► amzn.to/3bZVonJ
Clean Code
► amzn.to/32WVKq3
Introduction to Algorithms
► amzn.to/34SyVFP
Cracking the Coding Interview
► amzn.to/2QkdwC6
Índice:
Teoría 00:00
Anuncio 05:33
Empieza el código 06:00
Versión recursiva 08:15
Versión iterativa 13:55 - Věda a technologie
Este vídeo es la versión con el código arreglado! Disculpad las molestias y el error del anterior video!
El codigo esta disponible en el siguiente repositorio:
github.com/martincrb/binary-search-implementation
no vi los comentarios y me fui a escribir el codigo xd, a veces les agrego un time o chrono para ver que tal van de tiempo. Hay modos (herramientas, plugins) aparte de esos para ver qué tan rápido se compila y ejecuta el programa? (soy novato asi que no se que tan noob es la pregunta) excelente canal y excelentes aportes tocayo!
sos un capo... estaba pasando un momento oscuro en mi vida universitaria, habia un algoritmo que no podia entender ni resolver: estaba triste y frustrado, perdido diambulando por los pasillos de mi universidad. hasta que vi tu video. realmente me ayudaste a superar una etapa oscura en mi vida, me hiciste crecer profesionalmente. deberian llamarte el mesias de los algoritmos. gracias por tanto. cuando neceistes un amigo... aca estare siempre. saludos.
y que algoritmo era?
Ojalá así me hubieran explicado en la universidad, muy fácil de entender
Gracias!
Tu explicación me volvió a motivar a seguir estudiando programación, algo que me habían sacado los profes de este cuatrimestre. Gracias.
siempre me pregunto que demonios hago en la universidad, si mi universidad fue y será youtube, stackoverflow, y la experimentación al momento de programar, excelente video amigo.
Es cómico porque yo en un momento me hice la misma pregunta, lo único que me ofrecía la institución eran exámenes, el conocimiento lo recopilaba yo de stackoverflow. El contenido teórico que ofrecían los cursos universitarios estaban desactualizados por un par de años.
@@Lordcarlox a estas alturas sólo terminaré la carrera por el titulo solamente, aunque no todo es pérdida, la matemática que me enseñaron la universidad me ha servido bastante.
creo que es un error, simplificar las carreras de este ámbito en una universidad al mero hecho de programar o de hacer algoritmos, a mi la universidad me ayudo mucho con la parte analítica, la lógica y también a las metodologías para afrontar proyectos, por ejemplo, el como saber levantar información de un escenario en la vida real, o realizar "entregables" (documentación) y muchas otras cosas. Claro, estoy de acuerdo que los pensum universitarios a veces están un pelo por detrás de lo más actual, pero no se puede comparar con un stack overflow o you tube, son cosas totalmente distintas y ambas perfectamente son complementarias. Saludos
@@alexitox1993 Pero hay una gran diferencia, si tu universidad te enseñó todo eso, es porque esa universidad es buena y funciona, yo en cambio estudio en un país donde abunda la corrupción a niveles tan altos que los profesores ganan menos de un centavo de dólar por hora.
si vas a picar codigo como miles de autodidactas te sirve el youtube,
si quieres ser profesional no te sirve youtube.
Increible! Te pasaste!
Me recomendaron este canal para ir adquiriendo experiencia en programacion, y te juro explicas super bien y aplicable a varios lenguajes, ya que en si la logica es la misma, solo la estructuras segun el lenguaje. Un 10 estimado!
Yo también hice algo similar pero con valores de un e-commerce y la búsqueda tenía que encontrar en la list el valor más óptimo haciendo fórmulas para encontrar valores y que me de el valor faltante que estaba puesto en mensajes, era como un ML
Que paciencia y dedicación para explicar estos temas tenes!
Excelente video Martin! justo estoy estudiando algoritmos de busqueda en la universidad, y por lo que vi tambien se le llama busqueda dicotomica a este en particular. Con tu video queda clarisimo, segui asi. Saludos desde Argentina.
Gracias por tu video amigo, solo creo que olvidaste mencionar un dato importante, que descubrí cuando programé el algoritmo.
Este dato faltante es que cuando calculamos el punto mid, si el resultado es una fracción por ejemplo 3.5 o 0.5 debemos de redondear ese valor hacia arriba, es decir, a su entero superior; para el ejemplo que puse significa que ese 3.5 se debe redondear a 4 y ese 0.5 se debe de redondear a 1. Es importante hacerlo porque si no, el algoritmo no funcionará siempre.
Nota: Tambien puedes redondear hacia abajo pero eso implicaria mas cosas por hacer, lo mas facil es redondear hacia arriba. Pero estoy muy agradecido con tu explicacion Amigo me sirvió mucho. Gracias
Este es el pedacito de codigo que use para redondear hacia arriba, yo lo hice en lenguaje c#
double midDouble = Math.Ceiling(
left + (right - left) / 2
);
int mid = Convert.ToInt32(midDouble);
Amigo apenas descubrí tu canal, si hubiera tenido un profesor como tu en programación estructurada no habría sufrido tanto en la carrera jaja. Buen vídeo y un saludo.
magnífica explicación, sin dejar ningún detalle sin comentar! Felicidades
Tambien se puede utilizar la busqueda binaria para una busqueda en archivos, que si bien no son vectores, podemos abstraernos de eso para poder tratar un grupo de registros como si fueran indices de un vector (por lo menos en c)
Buen video, para complementar puedo indicar que la busqueda binaria ya viene implementada en C++, en los contenedores std:map y std:set, vía el método find.
Amigo soy suscriptor nuevo y te felicito, es un excelente canal, tienes sólo contenido de calidad. Meceres muchos más suscriptores.Saludos de chile!
Me gusto mucho este algoritmo, simple y potente. La explicación también excelente.
Para adaptarlo a JS tuve que colocar un Math.roud() en el calculo de mid para que me funcionara, no se si en c++ se redondea por defecto, muchas gracias por el video.
Excelente explicación, ya estoy suscrito al canal, espero que puedas subir mas videos de análisis del algoritmos.
Buen video, y muchas gracias. Realmente aprendo cosas nuevas en tu canal. 👍
Me encantan tus videos, espero mucho más contenido como esté.
Muy bueno el ejemplo del libro. En la universidad (Algoritmos y estructuras de datos) me lo enseñaron como "Búsqueda burbuja".
excelente algoritmo, BÚSQUEDA BINARIA, tanto en la presentación recursiva como iterativa, siento que el planteamiento comparativo ayuda mucho en la comprensión
además quedan implícitas las buenas prácticas al programar
más algoritmos por favor
¡Excelente video, muy bien explicado! 😄😄
Me la pase una hora entendiendo este método pero con solo 5 minutos en tu vídeo entendí todo muchas gracias
Por favor has uno sobre como anotar y resolver algunos problema como condicionales, for, funcion dentro de otra funcion, si retornar es una operacion, etc.
Muy buenos videos sigue asi
Buenas, esta muy bueno el canal y tus videos... Felicitaciones...
Puedes por favor recomendar libros sobre estos temas... De antemano gracias.
Que gran explicación. Excelente video :)
Wow en poco mas de 16 minutos me has dejado claro muchas cosas sobre el Binary Search, gracias!!
Con gusto! Gracias a ti por verme :)
Buen video, ameno, claro. Muchas gracias
Cada video mejor que el anterior, maestrazo
he estado viendo tus videos y no se por que aun no estaba suscrito, tu contenido es excelente!
Gracias!!!! 😍😍
Saludos buen vídeo, quería preguntar si puedes explicar el algoritmo de la burbuja, el mismo se usa para ordenar arrays, aunque soy nuevo viendo tus vídeos y no sé si lo hiciste
Gracias por tus explicaciones!
Excelente explicación !! 👍🏼👍🏼✌🏼
Muy bien explicado Martín, gracias!
Gracias a ti!
Es un canal bastante interesante, si alguna vez tengo la necesidad de programar en C, éste canal seria buena referencia.
Bettatech, eres oro puuuuuro 🎉🎉🙌
Excelente vídeo. Gracias Crack
Muy buen video como de costumbre, saludos desde Argentina
Gracias!!!
te ganaste otro suscriptor. Sigue así!
Muy bien explicado Betta muchas gracias ! no lo habia visto usando recursividad ;)
Gracias! Me alegra que te haya parecido util!
Hola. Viendo el video noto que en el primer ejemplo [4,1,3,5,2,6] no es aplicable la busqueda binaria, ya que cabe aclarar que esta busqueda sirve SOLO para arrays ordenados! Se podría ver algun algoritmo de ordenacion de paso o_O.
Me gustaria que hagas un video sobre el algoritmo de backtracking vs greedy. Saludos!
Es correcto porque sino está ordenado tendrías que hacer un burbuja por ejemplo para ordenar los números y eso se resume en otra iteración y cambia el coste del algoritmo
Hola excelente vídeo !!, muchas gracias. tengo una duda y es si este algoritmo puede ser aplicado a objetos o a un archivo, agradecería su respuesta.
Una consulta Betta, y los árboles binarios hechos por listas enlazadas para ambos lados, ahí aprendí sobre la búsqueda binaria y no es un array al que se accedan por índices o si? 🤔
Muy buen video.
Una consulta. No sería más eficiente continuar la búsqueda partiendo a la mitad los sucesivos trozos en los que se halla el objetivo, en lugar de ir achicando de a un solo paso por vez? Sería mucho más eficiente en arreglos muy grandes, y dejar la aproximación paso a paso solo cuando el trozo que queda del arreglo por analizar sea inferior a X elementos.
Muy buen canal! Saludos
¡Te amo Bro! ❤️
Oye bro una duda, el método buscar de list de c# usa búsqueda binaria?
me encantó la publicidad corta explícita concreta
Bueno video!!! una duda, que procede cuando quieres buscar en un JSON Array datos que contengan un valor en especifico? se puede usar este algoritmo?
Hola excelente video muchas gracias, una pregunta también este algoritmo podría usarse con objetos, supongamos tengo un arreglo de objetos dónde me interesa buscar en un atributo con valor de 100 si lo encuentra me retorne el objeto es posible esto?
este algoritmo solo sirve para hacer busquedas de datos de tipo numerico?
y si quisiera hacer busquedas en otros tipos de datos en un arreglo pero no quiero hacer busqueda secuencial?
Buen video
Es el que se usa en búsqueda con btree de postgresql no? Gracias por el aporte !
Buen vídeo. Podrías hacer un video de como usar funciones con parámetros ??
Que tipo de letra usas en tu terminal?
Me emocione porque hiciste el algoritmo con C++ jaja
Gracias betta, me encantan tus videos lindo UwU
Betta Tech Gracias de nuevo
No soy programador, pero esto me recuerda la demostración del método de la bisección, para encontrar la solución de una ecuación algebraica y la demostración del Teorema de Heine-Borel, para demostrar que toda sucesión en un intervalo cerrado, tiene una sub-sucesion convergente. Yo lo resumiría como, "cortar en dos y descartar". Me dieron ganas de volver programar, algo que no hago desde 1987.
Muy buena explicación, esta es la solución en Java:
public class Solution {
public Solution(){
// empty constructor
}
public static int binarySearch(int[] array, int target){
int iLeft = 0;
int iRight = array.length - 1;
while(iLeft target){
iRight = mid - 1;
} else {
iLeft = mid + 1;
}
}
return -1;
}
}
Busqueda sobre índices agrupados en bd.......... Buena extrapolación
Que podriamos hacer en el caso de que nuestro Array no este ordenado?
cual seria la mejor solucion?
Hola BettaTech. ¿Podrías hacer un vídeo, o aún mejor una série, en la que enseñes los detalles y alcances de los diferentes tipos de testing? Desde unit testing, pasando por integration testing y functional testing. Creo que sería de gran ayuda para muchos desarrolladores :).
Saludos.
Me parece una gran idea! Lo apunto, puede salir un video muy interesante 😁
Excelente explicación. Cuál es el tema que usas para el terminal de mac?
Horizon!
Hola hermano Buenas tardes excelente video Me encantó puedo hacerte una consulta yo tenía una duda de que si también se podría crear un algoritmo de búsqueda avanzada en internet es decir como el Buscador de Google que tiene La Barrita que si uno pone algo te lo va a buscar en Google Bueno hacer algo asi se puede?? crear un buscador y que ese buscador busque a travez de internet me explico🤔
Recuerda mucho a los métodos para resolver sistemas de ecuaciones lineales y no lineales.
Muy buen video
El coste de implementar está búsqueda binaria comparado con un BST (arbol binario búsqueda con listas enlazadas) es el mismo?
Si el vector esta ordenado si tendrian la misma complejidad O(log(n)). Mientras que si se hace a partir de un vector desordenado primero hay que ordenarlo y luego hacer la busqueda binaria, teniendo este caso mayor coste. Por eso las busquedas binarias estandarizadas se hacen con arboles binarios, que garantiza el ordenamiento de elementos, en vez de vectores que no aseguran el ordenamiento.
Por qué el tamaño del vector es la longitud del vector / por el elemento 0 ?
Que pasa si el vector ordenado empieza por 20 y sus elementos no son secuenciales ?
hola, estoy buscando como hacer un algoritmo de búsqueda que mediante palabras clave pueda encontrar toda la información relacionada,como se le llamaría a eso_
ECSELENTE VIDIO
Hola Betta Tech! ¿Este algoritmo también es aplicable a strings o existen algoritmos más eficientes para ello?
Hola Betta, tengo una pregunta tonta, no entiendo porque para calcular el mid point usas left + (right - left) / 2 en vez de (right + left) / 2
Yo creo que es más por legibilidad, es mucho más fácil de leer, left ( donde empezamos ) más la mitad. Pero realmente son lo mismo.
El resultado es el mismo, pero sumar right y left puede llevarte a un overflow si el tamaño del array esta cerca del limite de tamaño que cabe en un int, por lo que usas esa formula para evitar que se calcule un numero mas grande que right
Ooh que inteligente, muchas gracias!
BettaTech claro y es lógico porque eso mismo lo pones en el if
Para un vector que no esta ordenado cual seria el algoritmo apropiado? sin tener que ordenar el vector y luego aplicar este algoritmo.
Si no tienes información previa de algun tipo, siempre sera coste lineal. Es decir, recorrer el vector entero buscando tu item
Este algoritmo es eficiente como buscar en un árbol binario?
Excelente explicación, me ayudas mucho con tus videos Gracias.
Tiene el mismo coste que buscar en un arbol binario (caso medio O(logN)). Si te fijas en como compara, es como recorrer un arbol binario
Esto si es algoritmia de verdad
Ostras… me acabo de dar cuenta de que este algoritmo es superparecido al Teorema de Bolzano en matemáticas. Sin darme cuenta programé un algoritmo de búsqueda binaria cuando hice un programa que resolvía ecuaciones usando Bolzano JAJAJJAJ
pero en el primer arrai no habia orden, de menos a mayor como lo seria en las paginas de un libro.
Muy buen video 👏👏, ¿Que teclado es el que aparece en el vídeo?
Me gustaria saber, se ve bien cool
Creo es un teclado 60%, hay varios parecidos al que se ve en el directo. Podira ser un ck62 o un anne pro 2.
Es un Vortex pok3r :P
Que lenguaje usas?
C++, se sabe por la extensión .cpp
Hola betta, tengo una duda, la búsqueda binaria también sirve para objetos que no sean integers?
joshy23 si ósea mientras está en una lista
@@PositronQ claro, eso ya lo sé, pero este método a simple vista parece que solo funcionase con integers
Claro, haces un Array de objetos, y sobreescibes el método de comparación del objeto
@@paulino_acuna Claro, eso pensé pero en ese caso el objeto tendría que tener un atributo numérico para poder compararlos
Lo importante es que sean objetos ordenables!
Resubido? Bueno igual vuelvo a dejar mi like. Buen video!
Si, he reparado la parte del código que estaba mal para evitar confusiones!
@@BettaTech gracias! Por cierto, es pero que algun dia subas algo de los patrones Builder y Template method, son muy interesantes. Saludos!
de locos eso de la recursividad y la paranoia esa de vectore parece que estoy en matematicas de 4 de la eso con inma antekera
Está muy bien el ejercicio, podría añadirsele un timer de ejecución a cada búsqueda y poder ver los tiempos de ejecución para cada resultado 👍
No se si sea una pregunta muy tonta .. pero a que te refieres con costes?? Es Plata?? Espacio en memoria ?? Tiempo en hacer el algoritmo?? Todo?? No se ... me confundo cuando dices costes .
La pregunta es como aplicar esto en una matriz tridimensional
y en caso de que no estén ordenados?
En ese caso la búsqueda binaria no sirve, tendrías que buscar en el array completo y tendria coste lineal =(
De primera impresión me parece similar a los index utilizados en Mongo
No termino de comprender cómo calcula la mitad, ¿ no sería (izq+der)/2 ?
Buen vídeo, saludos
Fíjate en la forma recursiva. Después de la primera iteracion (en la que left es igual a 0), el subarray que comprueba después no empieza por 0, sino por mid + 1. Necesitas tener el offset (o el punto de origen del subarray) para poder calcular el punto medio del subarray, respecto al array original.
Cual es el lenguaje de programación usado en este video ?
C++
Es en termino simples para mi, el metodo de biseccion.
En donde esta programando? C++?
neovim, es un IDE para la consola
tengo una duda, mas de una vez, mis profesores de la carrera me han dicho que dentro de una misma función no puede haber mas de un return, y me tiraron por tierra un trabajo por ponerlos. ¿Por qué dicen que no se deben poner? o, ¿están ellos equivocados por decir eso y es una estupidez? gracias de antemano y muy buen video :D
estas diciendo q te dijeron q estas raspado por ejemplo tienes un if en el if pones un return y en el else otro_
@@robertoacosta5542 efectivamente si
El algoritmo es completamente funcional, similar a los arboles binarios, pero sirve solo para arrays ordenados
así que se llamaba búsqueda binaria, yo lo estuve haciendo desde hace un tiempo sin saber que era un método
porque simplemente no hacemos:
int mid = (left + right)/2;
en ves de:
int mid = left + (right - left)/2;
Porque para arrays muy muy grandes, left + right puede provocar overflow, en cambio con la segunda formula tienes siempre valores dentro de margen
@@BettaTech Muchas gracias por aclarar mi duda, lo cierto es que aun soy un novato.
Like y me suscribo.
En FullHD se le ocurrio andar a la camara
Ese algoritmo no se llama quickshort?
No, quicksort es un algoritmo de ordenamiento, este que expone el vídeo es un algoritmo de búsqueda
@@gabrielarana8939 ok, pero vamos que este pertenece al quicksort, ya que para ordenar tambien hay que hacer la misma busqueda, solo que ademas se van moviendo los datos.
En python todo esto se puede hacer con un simple "if x in array: print( array.index(x))"
en realidad XD
Desconozco como esta implementado el metodo index, pero si lo que hace es una busqueda para encontrar la primera aparicion, hacer eso tiene coste O(n), aunque sea una sola linea.
Otro tema es si ese metodo o el array de python indexan en un hash cada valor del array con sus posiciones, que nose si es el caso o no
@@BettaTech LA verdad es que tampoco sé como esta implementado, de hecho llevo con Phyton apenas unas semanas y antes de esto solo había programado en Arduino. Por lo que en general sé poco HAHAHAHA.
El caso es que para comprobar si es cuadrática, o no, he creado un array con valores del 1 al 10.000 y he usando la línea que he puesto en mi anterior comentario (realmente son 2 líneas por eso de mantener un orden en el código) y nos da el resultado de forma inmediata, por lo que deduzco que no tiene un coste cuadrático. Me equivoco?
@@TheGalox99 Tendrias que mirar como se degrada conforme aumentas el tamaño del array (100, 1000, 10000, 100000, 1000000 de elementos... etc) y mirar la grafica y ver la forma que tiene haha
@@BettaTech la cosa es que es literalmente instantaneo, he subido hasta 100000000 y sigue siendo instantaneo y si pongo un 0 más me da error de memoria.
Betta, me puedes responder a un email que te envié al correo que tienes en instagram hace una semana?
Perdon! Aun no he leido los mails, voy con bastante retraso a correos y mensajes de instagram 😓 Me intentare poner al dia en poco tiempo!
Buena explicación y lógica pero no es binaria, es balanceada, como en la estructura btree
Es el nombre del algoritmo, aunque tiene varios nombres:
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.