Español

Búsqueda: lineal y binaria

Educación secundaria básicaInformáticaBúsqueda exacta en un array ordenado de enteros pares únicos, índices basados en cero

Desbloquea este laboratorio con un pase

Un pase da acceso a todas las simulaciones del sitio, incluido el modo Presentación para clase. Los materiales didácticos de abajo siguen siendo gratuitos para todos.

Ver pasesYa tengo un pase

Pago único, sin suscripción.

Acerca de este experimento

Busca el mismo objetivo con la búsqueda lineal y la búsqueda binaria una al lado de la otra. En cada paso, cada algoritmo que aún no ha terminado realiza una comparación. La búsqueda binaria comprueba el punto medio de su intervalo ordenado restante; la búsqueda lineal avanza una posición cada vez. Selecciona un objetivo impar para ver cómo ambos algoritmos terminan sin encontrar una coincidencia.

Objetivos de aprendizaje

  • Sigue el intervalo de candidatos y el punto medio en la búsqueda binaria
  • Compara el número de comparaciones de la búsqueda lineal y la binaria
  • Explica por qué la búsqueda binaria requiere datos ordenados y cómo gestiona los objetivos ausentes

Cómo usarlo

  1. 1Busca 32 en el arreglo predeterminado, avanzando una comparación cada vez.
  2. 2Observa cuándo termina la búsqueda binaria y continúa hasta que termine la búsqueda lineal.
  3. 3Elige un objetivo impar, como 31. Observa cómo la búsqueda binaria llega a un intervalo vacío.
  4. 4Cambia la longitud del arreglo y busca su último valor. Compara los límites del peor caso.

El modelo

Punto medio de la búsqueda binaria para índices inferior y superior inclusivos
Cota superior del número de comparaciones de valores en la búsqueda binaria
Comparaciones en el peor caso para la búsqueda lineal mostrada

Supuestos

  • El array contiene los números enteros pares únicos 2, 4, ..., 2n en orden ascendente. Los índices comienzan en cero.
  • Una comparación de valores es una única comparación de tres vías con el valor objetivo. No se cuentan los cálculos de índices ni las comprobaciones del bucle.
  • Cuando el valor objetivo no está presente, la búsqueda lineal recorre todo el array, sin aprovechar el orden para detenerse antes.
  • Cada fila permanece en su estado finalizado mientras continúa la otra búsqueda. El intervalo de candidatos actual se muestra antes de aplicar el resultado de la comparación actual.

Pruébalo en clase

  1. Q1¿Por qué puede la búsqueda binaria descartar la mitad de las posiciones restantes tras una sola comparación?
  2. Q2¿Cuántas comparaciones se necesitan con cada método para encontrar el último valor de un array de 32 valores?
  3. Q3¿Qué falla si se aplica la misma regla del punto medio a un array desordenado?

Preguntas frecuentes

¿Por qué falla la búsqueda binaria con un valor objetivo impar?

Todas las entradas del array son pares. Por lo tanto, un valor objetivo impar nunca puede coincidir; el intervalo de candidatos acaba quedándose vacío y el algoritmo indica que no se ha encontrado.

¿Por qué ha dejado de avanzar una fila?

Esa búsqueda ya ha terminado. Al avanzar paso a paso, continúa el otro algoritmo para poder comparar sus costes totales de comparaciones.