¿Cuál es la diferencia entre la búsqueda lineal y la búsqueda binaria?

Question

¿Cuál es la diferencia entre la búsqueda lineal y la búsqueda binaria?

Answer 1

A linear search mira hacia abajo una lista, un elemento a la vez, sin saltar. En términos de complejidad, esta es una búsqueda de O(n): el tiempo necesario para buscar en la lista aumenta a la misma velocidad que la lista.

A binary search es cuando comienza con la mitad de una lista ordenada, y ve si es mayor o menor que el valor que está buscando, que determina si el valor está en la primera o segunda mitad de la lista . Salta a la mitad de la sublista y vuelve a comparar, etc. Así es como los humanos suelen buscar una palabra en un diccionario (aunque utilizamos una mejor heurística, obviamente, si estás buscando un "gato" no lo haces comenzar en "M"). En términos de complejidad, esta es una búsqueda O(log n): el número de operaciones de búsqueda crece más lentamente que la lista, porque se reduce a la mitad el "espacio de búsqueda" con cada operación.

Como ejemplo, supongamos que está buscando U en una lista de letras A-Z (índice 0-25; estamos buscando el valor en el índice 20).

una búsqueda lineal preguntaría:

list[0] == 'U'? No.
list[1] == 'U'? No.
list[2] == 'U'? No.
list[3] == 'U'? No.
list[4] == 'U'? No.
list[5] == 'U'? No.
... list[20] == 'U'? Sí. Terminado.

La búsqueda binaria preguntaría:

Compare list[12] ('M') con 'T': Más pequeño, mirar más allá. (Rango = 13-25)
Comparar list[19] ('T') con 'U': más pequeño, mire más adelante. (Rango = 20-25)
Comparar list[22] ('W') con 'U': más grande, mira antes. (Rango = 20-21)
Comparar list[20] ('U') con 'U': ¡Lo encontré! Terminado.

Al comparar los dos:

• La búsqueda binaria requiere los datos de entrada para ser ordenados; la búsqueda lineal no es
• La búsqueda binaria requiere un para hacer una comparación de; la búsqueda lineal solo requiere comparaciones de igualdad
• La búsqueda binaria tiene complejidad O (log n); la búsqueda lineal tiene complejidad O (n) como se discutió anteriormente
• La búsqueda binaria requiere acceso aleatorio a los datos; búsqueda lineal sólo requiere de acceso secuencial (esto puede ser muy importante - que significa una búsqueda lineal puede flujo de datos de tamaño arbitrario)

Answer 2

pensar en él como dos maneras diferentes de encontrar su camino en una agenda.Una búsqueda lineal comienza al principio, leyendo cada nombre hasta que encuentre lo que está buscando. Una búsqueda binaria, por el contrario, es cuando se abre el libro (por lo general en el centro), mira el nombre en la parte superior de la página, y decidir si el nombre que está buscando es más grande o más pequeña que la que 'que estas buscando. Si el nombre que estás buscando es más grande, entonces continúas buscando en la parte superior del libro de esta manera.

Answer 3

Una búsqueda lineal comienza al principio de una lista de valores y comprueba 1 por 1 para obtener el resultado que está buscando.

Una búsqueda binaria se inicia en el medio de una matriz ordenada y determina de qué lado (si existe) el valor que está buscando está activado. Esa "mitad" de la matriz se busca nuevamente de la misma manera, dividiendo los resultados en la mitad por dos cada vez.

Answer 4

me gustaría añadir una diferencia-

Para los valores de búsqueda lineales no necesitan ser ordenados.

Pero para búsqueda binaria los valores deben estar en el orden establecido.

Answer 5

La búsqueda lineal también conocida como búsqueda secuencial examina cada elemento en secuencia desde el inicio para ver si el elemento deseado está presente en la estructura de datos. Cuando la cantidad de datos es pequeña, esta búsqueda es fácil, pero fast.Its trabajo necesario es proporcional a la cantidad de datos que se searched.Doubling el número de elementos se duplicará el tiempo para buscar si el elemento deseado no está presente.

La búsqueda binaria es eficiente para la matriz más grande. En este comprobamos el medio element.If el valor es más grande que lo que estamos buscando, a continuación, busque en la primera mitad, de lo contrario, mira en la segunda mitad. Repita esto hasta que encuentre el artículo deseado. La tabla debe estar ordenada para búsqueda binaria. Elimina la mitad de los datos en cada iteración. Es logarítmico.

Si tenemos 1000 elementos para buscar, la búsqueda binaria requiere unos 10 pasos, la búsqueda lineal de 1000 pasos.

Answer 6

búsqueda binaria se agote el tiempo en O (log n), mientras que la búsqueda lineal se ejecuta en O (n) veces por lo tanto la búsqueda binaria tiene un mejor rendimiento

Answer 7

Asegúrese de deliberar sobre si la victoria de la búsqueda más rápida binario es la pena el costo de mantener ordenada la lista (para poder usar la búsqueda binaria). Es decir. si tiene muchas operaciones de inserción/eliminación y solo una búsqueda ocasional, la búsqueda binaria podría ser, en total, más lenta que la búsqueda lineal.

Answer 8

Pruebe esto: elija un nombre al azar "Apellido, nombre" y búsquelo en su directorio telefónico.

1ª vez: comience por el principio del libro, lea los nombres hasta que lo encuentre, o busque el lugar donde habría ocurrido alfabéticamente y tenga en cuenta que no está allí.

2da vez: abra el libro en el punto medio y mire la página. Pregúntese si esta persona debe estar a la izquierda o a la derecha. Cualquiera que sea, toma ese 1/2 y encuentra el medio. Repita este procedimiento hasta que encuentre la página donde debe estar la entrada y luego aplique el mismo proceso a las columnas, o simplemente busque linealmente los nombres en la página como antes.

¡Tiempo en ambos métodos y reporte!

[también considerar qué enfoque es mejor si todo lo que tienes es una lista de nombres, no solucionó ...]

Answer 9

una búsqueda lineal mira hacia abajo una lista, un elemento a la vez, sin saltar.En términos de complejidad, esta es una búsqueda O (n): el tiempo necesario para buscar en la lista aumenta con la misma velocidad que la lista.

Una búsqueda binaria es cuando comienza con la mitad de una lista ordenada, y ve si es mayor o menor que el valor que está buscando, que determina si el valor está en la primera o segunda mitad del lista. Salta a la mitad de la sublista y vuelve a comparar, etc. Así es como los humanos suelen buscar una palabra en un diccionario (aunque utilizamos una mejor heurística, obviamente, si estás buscando un "gato" no lo haces comenzar en "M"). En términos de complejidad, esta es una búsqueda O (log n): el número de operaciones de búsqueda crece más lentamente que la lista, porque se reduce a la mitad el "espacio de búsqueda" con cada operación.

Answer 10

una búsqueda lineal trabaja mirando a cada elemento de una lista de datos hasta que o bien se encuentra el destino o llega al final. Esto da como resultado el rendimiento de O (n) en una lista dada. Una búsqueda binaria viene con el requisito previo de que los datos deben estar ordenados. Podemos aprovechar esta información para disminuir el número de elementos que debemos observar para encontrar nuestro objetivo. Sabemos que si observamos un ítem aleatorio en los datos (digamos el ítem medio) y ese ítem es mayor que nuestro objetivo, entonces todos los ítems a la derecha de ese ítem también serán mayores que nuestro objetivo. Esto significa que solo tenemos que mirar la parte izquierda de los datos. Básicamente, cada vez que buscamos el objetivo y fallamos, podemos eliminar la mitad de los elementos restantes. Esto nos da una agradable complejidad de tiempo O (log n).

Recuerde que los datos de clasificación, incluso con el algoritmo más eficiente, siempre serán más lentos que una búsqueda lineal (los algoritmos de clasificación más rápidos son O (n * log n)). Por lo tanto, nunca debe ordenar los datos solo para realizar una búsqueda binaria única más adelante. Pero si va a realizar muchas búsquedas (digamos al menos O (log n) búsquedas), puede valer la pena ordenar los datos para que pueda realizar búsquedas binarias. También podría considerar otras estructuras de datos, como una tabla hash en tales situaciones.

Answer 11

Linear Search mira a través de los elementos hasta que encuentra el valor buscado.

Eficiencia: O(n)

Código Python Ejemplo:

test_list = [1, 3, 9, 11, 15, 19, 29] 
test_val1 = 25 
test_val2 = 15 

def linear_search(input_array, search_value): 
    index = 0 
    while (index < len(input_array)) and (input_array[index] < search_value): 
     index += 1 
    if index >= len(input_array) or input_array[index] != search_value: 
     return -1 

    return index 


print linear_search(test_list, test_val1) 
print linear_search(test_list, test_val2) 

Binary Search encuentra el elemento medio de la matriz. Comprueba que el valor medio es mayor o menor que el valor de búsqueda. Si es más pequeño, obtiene el lado izquierdo de la matriz y encuentra el elemento medio de esa parte. Si es mayor, obtiene la parte correcta de la matriz. Bucle la operación hasta que encuentre el valor buscado. O si no hay ningún valor en la matriz, finaliza la búsqueda.

Eficiencia: O(logn)

Código Python Ejemplo:

test_list = [1, 3, 9, 11, 15, 19, 29] 
test_val1 = 25 
test_val2 = 15 

def binary_search(input_array, value): 
    low = 0 
    high = len(input_array) - 1 
    while low <= high: 
     mid = (low + high)/2 
     if input_array[mid] == value: 
      return mid 
     elif input_array[mid] < value: 
      low = mid + 1 
     else: 
      high = mid - 1 

    return -1 


print binary_search(test_list, test_val1) 
print binary_search(test_list, test_val2) 

también se puede ver la información visualizada sobre Lineal y búsqueda binaria aquí: https://www.cs.usfca.edu/~galles/visualization/Search.html