La búsqueda binaria es una técnica utilizada para buscar elementos en una lista ordenada. En este artículo, veremos las funciones de la biblioteca para realizar búsquedas binarias. Encontrar la primera aparición de un elemento. bisect.bisect_left(a, x, lo=0, hi=len(a)) : Devuelve el punto de inserción más a la izquierda de x en una lista ordenada. Los … Continue reading «Búsqueda binaria (bisect) en Python»
En pocas palabras, este algoritmo de búsqueda aprovecha una colección de elementos que ya está ordenado al ignorar la mitad de los elementos después de una sola comparación. Compara x con el elemento del medio. Si x coincide con el elemento medio, devolvemos el índice medio. De lo contrario, si x es mayor que el … Continue reading «Programa Python para búsqueda binaria (recursiva e iterativa)»
Problema: Dada una array arr[] de n elementos, escriba una función para buscar un elemento dado x en arr[]. Ejemplos: Input : arr[] = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170} x = 110; Output : 6 Element x is present at index 6 Input : arr[] = {10, 20, 80, 30, … Continue reading «Programa de Python para búsqueda lineal»
Dado un texto txt[0..n-1] y un patrón pat[0..m-1], escriba una función search(char pat[], char txt[]) que imprima todas las apariciones de pat[] y su permutaciones (o anagramas) en txt[]. Puede suponer que n > m. La complejidad del tiempo esperado es O(n) Ejemplos: 1) Input: txt[] = «BACDGABCDA» pat[] = «ABCD» Output: Found at Index … Continue reading «Programa de Python para búsqueda de substrings de anagramas (o búsqueda de todas las permutaciones)»
Dado un texto txt[0..n-1] y un patrón pat[0..m-1], escriba una función de búsqueda (char pat[], char txt[]) que imprima todas las apariciones de pat[] en txt []. Puede suponer que n > m. Ejemplos: Input: txt[] = «THIS IS A TEST TEXT» pat[] = «TEST» Output: Pattern found at index 10 Input: txt[] = «AABAACAADAABAABA» … Continue reading «Programa de Python para el algoritmo de Rabin-Karp para la búsqueda de patrones»
Dado un texto txt[0..n-1] y un patrón pat[0..m-1] , escriba una función search(char pat[], char txt[]) que imprima todas las apariciones de pat[] en txt [] . Puede suponer que n > m . Ejemplos: Input: txt[] = «THIS IS A TEST TEXT» pat[] = «TEST» Output: Pattern found at index 10 Input: txt[] = «AABAACAADAABAABA» … Continue reading «Programa Python para el algoritmo KMP para la búsqueda de patrones»