Algoritmo de busqueda binaria en java

Algoritmo de busqueda binaria en java

Pseudocódigo de búsqueda binaria

Los desarrolladores nos enfrentamos a menudo a la tarea de determinar la posición de un elemento concreto en un array ordenado (o en una lista). Lo más sencillo sería recorrer la matriz de izquierda a derecha, comparando cada elemento con el que buscamos. Esto se llama “búsqueda lineal”.

Antes, si queríamos traducir una palabra desconocida, no teníamos una aplicación para ello. Teníamos que buscarla en un diccionario. En teoría, podíamos buscar la palabra concreta en todas las páginas, desde la parte superior izquierda hasta la inferior derecha, de adelante hacia atrás.

Si teníamos suerte, encontraríamos la palabra en las primeras páginas del libro. Si no tenemos suerte, no la encontraremos hasta casi el final del libro, o no la encontraremos en absoluto (no lo descubriríamos hasta la última página). Incluso con palabras que están relativamente lejos (como “búsqueda binaria”), tendríamos que buscar durante bastante tiempo de esta manera.

Por supuesto, nadie buscaría en un diccionario de esta manera. En su lugar, abrimos el libro por la mitad y vemos si la palabra viene alfabéticamente antes o después. Así sabemos en qué mitad del libro se encuentra la palabra y podemos ignorar la otra mitad. Después, volvemos a buscar en el centro y reducimos el área de búsqueda a la mitad una vez más (es decir, un cuarto en total). Con cada paso de búsqueda adicional, reducimos a la mitad el número de páginas restantes. De este modo, llegamos a la página objetivo -y en la página objetivo a la palabra que buscamos- en relativamente pocos pasos.

  Como hacer una app como uber

Ejemplo de búsqueda binaria

end procedureExplicación:Paso 1: Primero, compara x con el elemento del medio.Paso 2: Si x coincide con el elemento del medio, entonces tienes que devolver el índice del medio.Paso 3: Si no, si x es mayor que el elemento del medio, entonces x sólo puede estar en la mitad derecha del array después del elemento del medio. Paso 4: Else, si (x es menor) entonces recurre a la mitad izquierda.Así es como hay que buscar el elemento en el array dado.Veamos ahora cómo implementar un algoritmo de búsqueda binaria de forma recursiva. El siguiente programa demuestra lo mismo.Búsqueda binaria recursiva

Búsqueda binaria 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 una matriz ordenada.[4][5] La búsqueda binaria compara el valor objetivo con el elemento medio de la matriz. 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.

  Puntos maestros de auriculoterapia

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.

Búsqueda binaria (java recursivo)

El método java.util.Arrays.binarySearch(Object[] a, Object key) busca el objeto especificado en el array mediante el algoritmo de búsqueda binaria. Si no está ordenado, los resultados son indefinidos.

  Costo de instalacion de camaras de seguridad

Este método devuelve el índice de la clave de búsqueda, si está contenida en el array, sino devuelve (-(punto de inserción) – 1). El punto de inserción es el punto en el que se insertaría la clave en el array: el índice del primer elemento mayor que la clave, o a.length si todos los elementos del array son menores que la clave especificada.

Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad