Una implementación iterativa del popular algoritmo de búsqueda binaria para encontrar un elemento en una matriz ordenada.
¡Hola a todos! He publicado muchos artículos sobre algoritmos y estructuras de datos en mi blog, pero este es el primero aquí. En este artículo, examinaremos algoritmos fundamentales populares para entrevistas.
Sí, lo has adivinado bien: necesitas implementar una búsqueda binaria en Java, y necesitas escribir algoritmos de búsqueda binaria tanto iterativos como recursivos.
En informática, una búsqueda binaria, o búsqueda de medio intervalo, es un algoritmo de divide y vencerás que ubica la posición de un elemento en una matriz ordenada. La búsqueda binaria funciona comparando un valor de entrada con el elemento central de la matriz.
La comparación determina si el elemento es igual a la entrada, es menor que la entrada o es mayor que la entrada.
Cuando el elemento que se compara es igual a la entrada, la búsqueda se detiene y normalmente devuelve la posición del elemento.
Si el elemento no es igual a la entrada, se hace una comparación para determinar si la entrada es menor o mayor que el elemento.
Dependiendo del resultado, el algoritmo comienza de nuevo, pero solo busca en el subconjunto superior o inferior de los elementos de la matriz.
Si la entrada no se encuentra dentro de la matriz, el algoritmo generalmente generará un valor único que indica esto como -1 o simplemente lanzará una RuntimeException en Java como NoValueFoundException.
Los algoritmos de búsqueda binaria normalmente reducen a la mitad el número de elementos a verificar con cada iteración sucesiva, localizando así el elemento dado (o determinando su ausencia) en tiempo logarítmico.
Por cierto, si no está familiarizado con los algoritmos fundamentales de búsqueda y ordenación, también puede unirse a un curso como Estructuras de datos y algoritmos: inmersión profunda en Java para aprender algoritmos fundamentales.
Si Java no es su idioma de elección, puede encontrar más recomendaciones para JavaScript y Python en esta lista de cursos de algoritmos.
Por cierto, si prefiere los libros, le sugiero que lea un libro completo sobre algoritmos como Introducción a los algoritmos de Thomas H. Cormen.
Aquí hay un código de muestra que muestra la lógica de la búsqueda binaria iterativa en Java :
Implementación de búsqueda binaria en Java
Aquí hay un programa de muestra para implementar la búsqueda binaria en Java. El algoritmo se implementa de forma recursiva. Además, un dato interesante sobre la implementación de la búsqueda binaria en Java es que Joshua Bloch, autor del famoso libro Effective Java, escribió la búsqueda binaria en “java.util.Arrays”.
import java.util.Arrays;import java.util.Scanner;/** * Java program to implement Binary Search. We have implemented Iterative* version of Binary Search Algorithm in Java** @author Javin Paul*/public class IterativeBinarySearch { public static void main(String args[]) { int[] list = new int[]{23, 43, 31, 12}; int number = 12; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list)); binarySearch(list, 12); System.out.printf("Binary Search %d in integer array %s %n", 43, Arrays.toString(list)); binarySearch(list, 43); list = new int[]{123, 243, 331, 1298}; number = 331; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list)); binarySearch(list, 331); System.out.printf("Binary Search %d in integer array %s %n", 331, Arrays.toString(list)); binarySearch(list, 1333); // Using Core Java API and Collection framework // Precondition to the Arrays.binarySearch Arrays.sort(list); // Search an element int index = Arrays.binarySearch(list, 3);}/** * Perform a binary Search in Sorted Array in Java * @param input * @param number * @return location of element in array */public static void binarySearch(int[] input, int number) {int first = 0;int last = input.length - 1;int middle = (first + last) / 2;while (first <= last) { if (input[middle] < number) { first = middle + 1;} else if (input[middle] == number) {System.out.printf(number + " found at location %d %n", middle);break;} else { last = middle - 1;}middle = (first + last) / 2;}if (first > last) { System.out.println(number + " is not present in the list.\n");}}}OutputBinary Search 12 in integer array [12, 23, 31, 43]12 found at location 0Binary Search 43 in integer array [12, 23, 31, 43]43 found at location 3Binary Search 331 in integer array [123, 243, 331, 1298]331 found at location 2Binary Search 331 in integer array [123, 243, 331, 1298]1333 is not present in the list.Eso es todo sobre cómo implementar la búsqueda binaria usando la recursividad en Java . Junto con la búsqueda lineal, estos son dos de los algoritmos de búsqueda esenciales que aprende en su clase de informática.
La estructura de datos del árbol de búsqueda binaria aprovecha este algoritmo y organiza los datos en una estructura jerárquica para que pueda buscar cualquier nodo en el tiempo O (logN).
Sin embargo, debe recordar que para usar la búsqueda binaria, necesita una lista o matriz ordenada, por lo que también debe considerar el costo de la clasificación cuando considere usar un algoritmo de búsqueda binaria en el mundo real.
Aprendizaje adicional
Estructuras de datos y algoritmos: análisis profundo con Java
Algoritmos y estructuras de datos: parte 1 y 2
Estructuras de datos en Java 9 por Heinz Kabutz
10 libros de algoritmos para entrevistas
10 cursos de estructura de datos y algoritmos para entrevistas
5 cursos gratuitos para aprender la estructura de datos y los algoritmos
Otros tutoriales de estructura de datos y algoritmos que le pueden gustar
- ¿Cómo implementar el algoritmo Quicksort en Java? (tutorial)
- ¿Cómo implementar el árbol de búsqueda binaria en Java? (solución)
- ¿Cómo implementar el algoritmo Quicksort sin recursividad? (tutorial)
- ¿Cómo implementar el algoritmo de ordenación por inserción en Java? (tutorial)
- ¿Cómo implementar el algoritmo de clasificación de burbujas en Java? (tutorial)
- ¿Cuál es la diferencia entre el algoritmo de clasificación basado en comparación y sin comparación? (responder)
- ¿Cómo implementar Bucket Sort en Java? (tutorial)
- ¿Cómo implementar un algoritmo de búsqueda binaria sin recursividad en Java? (tutorial)
- Más de 50 cursos de estructura de datos y algoritmos para programadores (preguntas)
Gracias por leer este artículo. Si te gusta este artículo, compártelo con tus amigos y colegas. Si tiene alguna sugerencia o comentario, deje un comentario.