algorithm
buscando
Buscar..
Búsqueda binaria
Introducción
Binary Search es un algoritmo de búsqueda Dividir y Conquistar. Utiliza O(log n) tiempo para encontrar la ubicación de un elemento en un espacio de búsqueda donde n es el tamaño del espacio de búsqueda.
La búsqueda binaria funciona dividiendo a la mitad el espacio de búsqueda en cada iteración después de comparar el valor objetivo con el valor medio del espacio de búsqueda.
Para utilizar la búsqueda binaria, el espacio de búsqueda debe ordenarse (ordenarse) de alguna manera. Las entradas duplicadas (las que se comparan como iguales según la función de comparación) no se pueden distinguir, aunque no violan la propiedad de búsqueda binaria.
Convencionalmente, usamos menos de (<) como función de comparación. Si a <b, devolverá verdadero. si a no es menor que b y b no es menor que a, a y b son iguales.
Ejemplo de pregunta
Eres un economista, aunque bastante malo. Se le asigna la tarea de encontrar el precio de equilibrio (es decir, el precio donde la oferta = demanda) para el arroz.
Recuerde que cuanto mayor sea el precio, mayor será la oferta y menor la demanda.
Como su compañía es muy eficiente en el cálculo de las fuerzas del mercado, puede obtener instantáneamente la oferta y la demanda en unidades de arroz cuando el precio del arroz se establece a un precio determinado p .
Su jefe desea el precio de equilibrio CUANTO ANTES, pero le dice que el precio de equilibrio puede ser un número entero positivo que sea a lo sumo 10^17 y se garantiza que exista exactamente una solución de número entero positivo en el rango. ¡Así que sigue con tu trabajo antes de que lo pierdas!
Se le permite llamar a las funciones getSupply(k) y getDemand(k) , que harán exactamente lo que se indica en el problema.
Explicación de ejemplo
Aquí nuestro espacio de búsqueda es de 1 a 10^17 . Así, una búsqueda lineal es inviable.
Sin embargo, observe que a medida que k aumenta, getSupply(k) aumenta y getDemand(k) disminuye. Por lo tanto, para cualquier x > y , getSupply(x) - getDemand(x) > getSupply(y) - getDemand(y) . Por lo tanto, este espacio de búsqueda es monotónico y podemos utilizar la búsqueda binaria.
El siguiente psuedocode demuestra el uso de la búsqueda binaria:
high = 100000000000000000 <- Upper bound of search space
low = 1 <- Lower bound of search space
while high - low > 1
mid = (high + low) / 2 <- Take the middle value
supply = getSupply(mid)
demand = getDemand(mid)
if supply > demand
high = mid <- Solution is in lower half of search space
else if demand > supply
low = mid <- Solution is in upper half of search space
else <- supply==demand condition
return mid <- Found solution
Este algoritmo se ejecuta en tiempo ~O(log 10^17) . Esto se puede generalizar a ~O(log S) de tiempo en la que S es el tamaño del espacio de búsqueda, ya que en cada iteración del while de bucle, que reduce a la mitad el espacio de búsqueda (de [baja: alta] a cualquiera [baja: mediados] o [medio: alto] ).
C Implementación de búsqueda binaria con recursión.
int binsearch(int a[], int x, int low, int high) {
int mid;
if (low > high)
return -1;
mid = (low + high) / 2;
if (x == a[mid]) {
return (mid);
} else
if (x < a[mid]) {
binsearch(a, x, low, mid - 1);
} else {
binsearch(a, x, mid + 1, high);
}
}
Búsqueda binaria: en números ordenados
Es más fácil mostrar una búsqueda binaria en números usando pseudocódigo
int array[1000] = { sorted list of numbers };
int N = 100; // number of entries in search space;
int high, low, mid; // our temporaries
int x; // value to search for
low = 0;
high = N -1;
while(low < high)
{
mid = (low + high)/2;
if(array[mid] < x)
low = mid + 1;
else
high = mid;
}
if(array[low] == x)
// found, index is low
else
// not found
No intente regresar temprano comparando array [mid] con x para la igualdad. La comparación adicional solo puede ralentizar el código. Tenga en cuenta que debe agregar uno a bajo para evitar quedar atrapado por la división de enteros siempre redondeando hacia abajo.
Curiosamente, la versión anterior de la búsqueda binaria le permite encontrar la aparición más pequeña de x en la matriz. Si la matriz contiene duplicados de x, el algoritmo se puede modificar ligeramente para que devuelva la mayor aparición de x simplemente agregando a la condicional de condicional:
while(low < high)
{
mid = low + ((high - low) / 2);
if(array[mid] < x || (array[mid] == x && array[mid + 1] == x))
low = mid + 1;
else
high = mid;
}
Tenga en cuenta que en lugar de hacer mid = (low + high) / 2 , también puede ser una buena idea probar mid = low + ((high - low) / 2) para implementaciones como las implementaciones de Java para reducir el riesgo de obtener un Desbordamiento para insumos realmente grandes.
Busqueda lineal
La búsqueda lineal es un algoritmo simple. Recorre los elementos hasta que se encuentra la consulta, lo que lo convierte en un algoritmo lineal: la complejidad es O (n), donde n es el número de elementos que se deben revisar.
¿Por qué O (n)? En el peor de los casos, tienes que pasar por todos los n elementos.
Puede compararse con la búsqueda de un libro en una pila de libros: recorre todos ellos hasta encontrar el que desea.
A continuación se muestra una implementación de Python:
def linear_search(searchable_list, query):
for x in searchable_list:
if query == x:
return True
return False
linear_search(['apple', 'banana', 'carrot', 'fig', 'garlic'], 'fig') #returns True
Rabin Karp
El algoritmo de Rabin-Karp o el algoritmo de Karp-Rabin es un algoritmo de búsqueda de cadenas que utiliza el hash para encontrar cualquiera de un conjunto de cadenas de patrones en un texto. Su tiempo promedio y el mejor de los casos es O (n + m) en el espacio O ( p), pero su tiempo en el peor de los casos es O (nm) donde n es la longitud del texto y m es la longitud del patrón.
Implementación de algoritmos en java para la coincidencia de cadenas
void RabinfindPattern(String text,String pattern){
/*
q a prime number
p hash value for pattern
t hash value for text
d is the number of unique characters in input alphabet
*/
int d=128;
int q=100;
int n=text.length();
int m=pattern.length();
int t=0,p=0;
int h=1;
int i,j;
//hash value calculating function
for (i=0;i<m-1;i++)
h = (h*d)%q;
for (i=0;i<m;i++){
p = (d*p + pattern.charAt(i))%q;
t = (d*t + text.charAt(i))%q;
}
//search for the pattern
for(i=0;i<end-m;i++){
if(p==t){
//if the hash value matches match them character by character
for(j=0;j<m;j++)
if(text.charAt(j+i)!=pattern.charAt(j))
break;
if(j==m && i>=start)
System.out.println("Pattern match found at index "+i);
}
if(i<end-m){
t =(d*(t - text.charAt(i)*h) + text.charAt(i+m))%q;
if(t<0)
t=t+q;
}
}
}
Al calcular el valor hash, lo estamos dividiendo por un número primo para evitar la colisión. Después de dividir por el número primo, las posibilidades de colisión serán menores, pero aún existe la posibilidad de que el valor hash pueda ser el mismo para dos cadenas, por lo que conseguimos una coincidencia que tenemos que verificar personaje por personaje para asegurarnos de que obtenemos una coincidencia adecuada.
t = (d * (t - text.charAt (i) * h) + text.charAt (i + m))% q;
Esto es para recalcular el valor de hash para el patrón, primero eliminando el carácter más a la izquierda y luego agregando el nuevo carácter del texto.
Análisis de búsqueda lineal (peor, promedio y mejores casos)
Podemos tener tres casos para analizar un algoritmo:
Peor de los casos
Caso medio
Mejor caso
#include <stdio.h> // Linearly search x in arr[]. If x is present then return the index, // otherwise return -1 int search(int arr[], int n, int x) { int i; for (i=0; i<n; i++) { if (arr[i] == x) return i; } return -1; }/ * Programa controlador para probar las funciones anteriores * /
int main() { int arr[] = {1, 10, 30, 15}; int x = 30; int n = sizeof(arr)/sizeof(arr[0]); printf("%d is present at index %d", x, search(arr, n, x)); getchar(); return 0; }
Análisis de los peores casos (generalmente hecho)
En el peor análisis de caso, calculamos el límite superior del tiempo de ejecución de un algoritmo. Debemos conocer el caso que provoca la máxima cantidad de operaciones a ejecutar. Para la búsqueda lineal, el caso más desfavorable ocurre cuando el elemento a buscar (x en el código anterior) no está presente en la matriz. Cuando x no está presente, las funciones de búsqueda () lo comparan con todos los elementos de arr [] uno por uno. Por lo tanto, la complejidad en el peor de los casos de la búsqueda lineal sería Θ (n)
Análisis de casos promedio (a veces hecho)
En el análisis de casos promedio, tomamos todas las entradas posibles y calculamos el tiempo de cálculo para todas las entradas. Sume todos los valores calculados y divida la suma por el número total de entradas. Debemos conocer (o predecir) la distribución de los casos. Para el problema de búsqueda lineal, supongamos que todos los casos se distribuyen uniformemente (incluido el caso de que x no esté presente en la matriz). Entonces sumamos todos los casos y dividimos la suma por (n + 1). A continuación se muestra el valor de la complejidad media de tiempo de caso.
Mejor análisis de caso (Bogus)
En el mejor análisis de casos, calculamos el límite inferior del tiempo de ejecución de un algoritmo. Debemos conocer el caso que causa la cantidad mínima de operaciones a ejecutar. En el problema de búsqueda lineal, el mejor caso ocurre cuando x está presente en la primera ubicación. El número de operaciones en el mejor de los casos es constante (no depende de n). Entonces, la complejidad del tiempo en el mejor de los casos sería Θ (1) La mayoría de las veces, hacemos el análisis del peor de los casos para analizar algoritmos. En el peor de los análisis, garantizamos un límite superior en el tiempo de ejecución de un algoritmo que es buena información. El análisis de casos promedio no es fácil de hacer en la mayoría de los casos prácticos y rara vez se realiza. En el análisis de casos promedio, debemos conocer (o predecir) la distribución matemática de todas las entradas posibles. El mejor análisis de casos es falso. Garantizar un límite inferior en un algoritmo no proporciona ninguna información, como en el peor de los casos, un algoritmo puede tardar años en ejecutarse.
Para algunos algoritmos, todos los casos son asintóticamente iguales, es decir, no hay peores ni mejores casos. Por ejemplo, Merge Sort. Merge Sort realiza operaciones Θ (nLogn) en todos los casos. La mayoría de los otros algoritmos de clasificación tienen peores y mejores casos. Por ejemplo, en la implementación típica de Ordenación rápida (donde el pivote se elige como elemento de esquina), lo peor ocurre cuando la matriz de entrada ya está ordenada y lo mejor ocurre cuando los elementos pivote siempre dividen la matriz en dos mitades. Para la ordenación por inserción, el peor de los casos ocurre cuando la matriz se ordena en orden inverso y el mejor caso ocurre cuando la matriz se ordena en el mismo orden que la salida.