algorithm - qué - ¿Cuál es la diferencia entre la búsqueda lineal y la búsqueda binaria?

busqueda lineal en java

Question

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

Answer 1

Asegúrese de deliberar si la ganancia de la búsqueda binaria más rápida vale 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 2

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

Primera vez: comience al principio del libro, lea los nombres hasta que lo encuentre, o busque el lugar donde habría ocurrido alfabéticamente y observe 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.

¡Controle ambos métodos e informe!

[también considere qué enfoque es mejor si todo lo que tiene es una lista de nombres, no ordenados ...]

Answer 3

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 rápida. Es fácil pero el trabajo necesario es proporcional a la cantidad de datos que se buscarán. Duplicar el número de elementos duplicará el tiempo para buscar si el elemento deseado no está presente.

La búsqueda binaria es eficiente para una matriz más grande. En esto comprobamos el elemento medio. Si el valor es más grande que lo que estamos buscando, busque en la primera mitad, de lo contrario, busque 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 toma alrededor de 10 pasos, la búsqueda lineal 1000 pasos.

Answer 4

Para una comprensión clara, echa un vistazo a las implementaciones de mi codepen https://codepen.io/serdarsenay/pen/XELWqN

La mayor diferencia es la necesidad de ordenar la muestra antes de aplicar la búsqueda binaria, por lo tanto, para la mayoría de las muestras de "tamaño normal" (lo que significa que se discutirá) será más rápido buscar con un algoritmo de búsqueda lineal.

Aquí está el código de javascript, para html y css y el ejemplo de ejecución completo, consulte el enlace de codepen anterior.

var unsortedhaystack = [];
var haystack = [];
function init() {
  unsortedhaystack = document.getElementById("haystack").value.split('' '');
}
function sortHaystack() {
  var t = timer(''sort benchmark'');
  haystack = unsortedhaystack.sort();
  t.stop();
}

var timer = function(name) {
    var start = new Date();
    return {
        stop: function() {
            var end  = new Date();
            var time = end.getTime() - start.getTime();
            console.log(''Timer:'', name, ''finished in'', time, ''ms'');
        }
    }
};

function lineerSearch() {
  init();
  var t = timer(''lineerSearch benchmark'');
  var input = this.event.target.value;
  for(var i = 0;i<unsortedhaystack.length - 1;i++) {
    if (unsortedhaystack[i] === input) {
      document.getElementById(''result'').innerHTML = ''result is... "'' + unsortedhaystack[i] + ''", on index: '' + i + '' of the unsorted array. Found'' + '' within '' + i + '' iterations'';
      console.log(document.getElementById(''result'').innerHTML);
      t.stop(); 
      return unsortedhaystack[i]; 
    }
  }
}

function binarySearch () {
  init();
  sortHaystack();
  var t = timer(''binarySearch benchmark'');
  var firstIndex = 0;
  var lastIndex = haystack.length-1;
  var input = this.event.target.value;

  //currently point in the half of the array
  var currentIndex = (haystack.length-1)/2 | 0;
  var iterations = 0;

  while (firstIndex <= lastIndex) {
    currentIndex = (firstIndex + lastIndex)/2 | 0;
    iterations++;
    if (haystack[currentIndex]  < input) {
      firstIndex = currentIndex + 1;
      //console.log(currentIndex + " added, fI:"+firstIndex+", lI: "+lastIndex);
    } else if (haystack[currentIndex] > input) {
      lastIndex = currentIndex - 1;
      //console.log(currentIndex + " substracted, fI:"+firstIndex+", lI: "+lastIndex);
    } else {
      document.getElementById(''result'').innerHTML = ''result is... "'' + haystack[currentIndex] + ''", on index: '' + currentIndex + '' of the sorted array. Found'' + '' within '' + iterations + '' iterations'';
      console.log(document.getElementById(''result'').innerHTML);
      t.stop(); 
      return true;
    }
  }
}

Answer 5

Piense en ello como dos formas diferentes de encontrar su camino en una guía telefónica. 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 abre el libro (generalmente en el medio), mira el nombre en la parte superior de la página y decide si el nombre que está buscando es más grande o más pequeño que el que usted ''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 6

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 comienza en el medio de una matriz ordenada, y determina de qué lado (si es que hay alguno) 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 7

Una búsqueda lineal funciona al observar cada elemento en una lista de datos hasta que encuentra el objetivo 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 ser 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).

Solo recuerda 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 8

Una búsqueda lineal mira hacia abajo en 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 el medio de una lista ordenada y ve si es mayor o menor que el valor que está buscando, lo 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.

Answer 9

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

Answer 10

Linear Search examina los elementos hasta que encuentra el valor buscado.

Eficiencia: O(n)

Ejemplo de código de Python:

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)

Ejemplo de código de Python:

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 puede ver información visualizada sobre Búsqueda lineal y binaria aquí: https://www.cs.usfca.edu/~galles/visualization/Search.html

Answer 11

Una búsqueda lineal mira hacia abajo en 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 el medio de una lista ordenada y ve si es mayor o menor que el valor que está buscando, lo 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 AZ (í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:

Compara la list[12] (''M'') con ''U'': más pequeña, mira más allá. (Rango = 13-25)
Compare la list[19] (''T'') con ''U'': más pequeña, mire más allá. (Rango = 20-25)
Compara la list[22] (''W'') con ''U'': más grande, mira antes. (Rango = 20-21)
Compara la list[20] (''U'') con ''U'': ¡Lo encontraste! Terminado.

Comparando los dos:

• La búsqueda binaria requiere que los datos de entrada sean ordenados; la búsqueda lineal no
• La búsqueda binaria requiere una comparación de pedidos ; 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; la búsqueda lineal solo requiere acceso secuencial (esto puede ser muy importante, significa que una búsqueda lineal puede transmitir datos de tamaño arbitrario)