“Una tabla con punteros” es una descripción bastante vaga de una estructura de datos. Una lista de cadenas en Python es una tabla con punteros (una cadena de Python se representa como un puntero a los datos de caracteres subyacentes), y ciertamente puede hacer una búsqueda binaria en una lista ordenada de cadenas de Python. Puede construir estructuras de datos análogas en otros idiomas, y nuevamente la búsqueda binaria puede ser un algoritmo adecuado para buscarla.
Hay dos características clave que una estructura de datos debe tener para que la búsqueda binaria sea adecuada. Primero, obviamente, es que debe representar una secuencia ordenada (ya debe estar en orden ordenado), porque de lo contrario sondear el elemento del medio no le permite eliminar la región anterior o posterior. Segundo, probablemente más relevante para su pregunta, es que acceder al elemento medio debe ser una operación de tiempo constante. Si la colección se representa como una región contigua de memoria (como una matriz en Java, una lista en Python y estructuras similares en otros idiomas), la indexación del elemento central se realiza mediante un cálculo en direcciones de memoria en tiempo constante, independientemente de si el contenido del elemento intermedio contiene punteros. Pero si la colección en sí es una estructura vinculada, como una lista vinculada, entonces no es posible acceder al elemento intermedio en tiempo constante. Por ejemplo, en una estructura de lista vinculada estándar, el acceso al elemento 200 se realiza accediendo al elemento 1, luego al elemento 2, y así sucesivamente hasta que se alcanza el elemento 200. En este caso, se pierde toda la ventaja de la búsqueda binaria.
Si va a usar punteros para una colección que se mantiene en orden, en lugar de poner el elemento más pequeño primero, puede hacer que el encabezado de la lista sea el elemento central, y en lugar de un puntero al siguiente elemento, use dos: uno a una colección de elementos que son “antes” del elemento medio, y uno a una colección de elementos que son “después” del elemento medio. Cada una de estas colecciones se ordena de la misma manera, con su elemento central en la cabeza y dos enlaces a grupos de elementos antes y después. Si puede mantener aproximadamente la mitad de los elementos a la izquierda y la mitad a la derecha en cada paso, entonces esencialmente ha representado el paso “dividir en la mitad” de la búsqueda binaria directamente en la estructura de datos. Eso se llama un “árbol de búsqueda”, y hay un montón de trabajo sobre cómo mantener la estructura para que cada paso de la búsqueda divida la colección aproximadamente a la mitad, como la búsqueda binaria. Incluso puede generalizar eso con más punteros de cada elemento, dividiendo la colección en piezas más pequeñas en cada paso. La lógica subyacente es muy parecida a la búsqueda binaria, pero como no podemos dividir la colección en partes indexando un elemento en un área contigua de memoria, usamos los punteros para encontrar partes cada vez más pequeñas de la colección.
- ¿Cuál es el mejor algoritmo para encontrar el camino con dos limitaciones?
- ¿Cuáles son las ventajas de la agrupación de K-Means?
- Dada una biblioteca que proporciona una coincidencia aproximada de cadenas, ¿cuáles son algunos procedimientos adicionales que pueden explicar una mejor coincidencia de cadenas?
- ¿Puedes dar ejemplos de cómo usamos las estructuras de datos en el mundo real?
- Cómo diseñar una nueva función heurística admisible para un algoritmo A * para resolver el problema del mosaico deslizante
