Ver 4+ más
Introducción a la búsqueda binaria en PythonEl proceso de encontrar un elemento de una colección de elementos se conoce como búsqueda. Tenemos varias técnicas o formas de buscar un elemento entre varios elementos dados, y estas técnicas se conocen como algoritmos de búsqueda. La búsqueda binaria es uno de los algoritmos de búsqueda más sencillos. Conozcamos la búsqueda binaria en python.La búsqueda binaria en python es una técnica de búsqueda que funciona en un array o lista de elementos ordenados. En lugar de comparar cada elemento de la lista con el elemento requerido, el algoritmo de búsqueda binaria divide repetidamente la lista de elementos en segmentos más pequeños. A continuación, busca el elemento necesario en los segmentos divididos.
Búsqueda binaria iterativaAhora vamos a discutir el enfoque iterativo para implementar la búsqueda binaria. Supongamos que queremos buscar el mismo elemento E en el array, y podemos llamar a una función en el array con el elemento E requerido: BinarySearch(array, E). Esta función devolverá el índice del elemento E.
Ordenación rápida en python
En informática, la búsqueda binaria, también conocida como búsqueda de medio intervalo,[1] búsqueda logarítmica,[2] o corte binario,[3] es un algoritmo de búsqueda que encuentra la posición de un valor objetivo dentro de un array ordenado.[4][5] La búsqueda binaria compara el valor objetivo con el elemento medio del array. Si no son iguales, la mitad en la que no puede estar el objetivo se elimina y la búsqueda continúa en la mitad restante, tomando de nuevo el elemento central para compararlo con el valor objetivo, y repitiendo esto hasta que se encuentre el valor objetivo. Si la búsqueda termina con la mitad restante vacía, el objetivo no está en la matriz.
La búsqueda binaria es más rápida que la búsqueda lineal, excepto para matrices pequeñas. Sin embargo, el array debe ser ordenado primero para poder aplicar la búsqueda binaria. Existen estructuras de datos especializadas diseñadas para la búsqueda rápida, como las tablas hash, que pueden buscarse de forma más eficiente que la búsqueda binaria. Sin embargo, la búsqueda binaria puede utilizarse para resolver una gama más amplia de problemas, como encontrar el siguiente elemento más pequeño o el siguiente elemento más grande de la matriz en relación con el objetivo, incluso si está ausente de la matriz.
Comentarios
Una búsqueda binaria es un método para localizar un determinado elemento en una lista. En este tutorial, realizaremos una operación de búsqueda binaria para descubrir la posición del índice de un elemento en una lista con dos métodos diferentes.
La búsqueda binaria es el programa más popular para realizar búsquedas. Supongamos que tenemos una lista de mil elementos y necesitamos obtener la posición del índice de una entrada específica. Utilizando la técnica de búsqueda binaria, podemos determinar rápidamente la posición del índice de un elemento. Para utilizar el método de búsqueda binaria, las entradas de la lista deben estar ordenadas. Si los componentes no están ya ordenados, ordénelos primero. Para ejecutar la búsqueda binaria podemos seguir dos enfoques que se comentan a continuación:
En este método, iteraremos por toda la lista, repitiendo una serie de instrucciones. Seguiremos buscando el valor del medio hasta encontrarlo. Veamos el algoritmo seguido del código para una mejor comprensión:
En la búsqueda binaria se puede utilizar la recursión. Crearemos una función recursiva que se llame a sí misma hasta que se cumpla la condición. El enfoque recursivo sigue el método “divide y vencerás”, que es un método para resolver un problema complejo dividiéndolo en subproblemas más pequeños, resolviéndolos y combinándolos para obtener el resultado deseado. Veamos el algoritmo seguido del código para una mejor comprensión:
Búsqueda lineal
Es importante tener en cuenta que, para poder utilizar la búsqueda binaria, los datos deben estar ordenados. Algunas personas se confunden con los algoritmos de ordenación y los de búsqueda, agrupándolos en su pensamiento, pero vale la pena tomarse un momento para organizar un poco su “caja de herramientas de algoritmos” y asegurarse de que la búsqueda y la ordenación tienen cada una su propia sección. A modo de recordatorio, vea estas listas para ver algunos ejemplos de cada uno:
Este artículo trata sobre la búsqueda binaria y cómo escribirla usando Python. Antes de escribirlo en código o pseudocódigo, necesitas entender el proceso a fondo, y esto se hace mejor haciendo muchos ejemplos a mano en papel o en una pizarra. Puedes obtener una muy buena intuición de cómo funciona el algoritmo jugando a las adivinanzas con un amigo.
Si juegas unas cuantas veces a este juego, descubrirás rápidamente que algunas estrategias para adivinar el número son más eficaces que otras. Por ejemplo, imagina que el número original es el 13 y tú adivinas el 50. Te dicen que tu apuesta es demasiado alta. Adivinar el 49 a continuación no sería una buena opción. Para optimizar sus posibilidades de adivinar el número en el menor número de intentos posible, la mejor estrategia es adivinar a medio camino entre los límites superior e inferior conocidos para el valor real. Así, si sabe que el número está entre 1 y 64, debería adivinar 32. Si te dicen que es demasiado alto, debes adivinar 16, y así sucesivamente. Cada vez se reduce a la mitad el espacio de búsqueda, lo que significa que se garantiza que se obtendrá la respuesta en relativamente pocos pasos. Esta es la esencia del funcionamiento de la búsqueda binaria.