¿Está deletreado correctamente "seperar"?

En esta página, utilizarás un algoritmo de búsqueda binaria para buscar eficientemente en una lista ordenada.

Responder esta pregunta es fácil en Snap!, porque puedes solo preguntar (100,000 palabras) contiene (seperar). Pero "fácil" no significa rápido. El bloque contiene todavía tiene que buscar cada elemento de la lista hasta que encuentre el que está buscando (y decir verdadero) o alcanzar el final de la lista (y decir falso).

Cuando estás buscando una sola cosa en una lista (por ejemplo, revisando si una palabra en particular está escrita correctamente) en vez de encontrar todas las palabras con algunas características (por ejemplo, buscar todas las palabras de cinco letras), puedes utilizar la estrategia de Página 1: Adivina mi número para hacer tu algoritmo más rápido. La mejor estrategia para ese problema es un algoritmo de búsqueda binaria: siempre adivina el valor medio. De esa manera, eliminas la mitad de las posibilidades con cada adivinanza. Podemos utilizar una estrategia similar para buscar una palabra en una lista de palabras.

Podrías haber escrito un programa de adivinanza de números más sencillo: la computadora podría adivinar el número 1, luego el 2, luego el 3, y así sucesivamente hasta encontrar el número. Eso sería un algoritmo de búsqueda lineal; es más fácil de codificar, pero tarda más en ejecutarse porque cada vez que hace una adivinanza errónea, elimina solo esa adivinanza. Con la búsqueda binaria, cada adivinanza incorrecta elimina la mitad de posibilidades a la vez.
: Búsqueda binaria
AAP-2.P.1, AAP-2.P.2

Un algoritmo de búsqueda binaria (binary search) comienza en medio de una lista ordenada y elimina repetidamente la mitad de la lista hasta que se encuentra el valor deseado o se han eliminado todos los elementos.

AAP-2.O.1
Aprendiste acerca de lista transpuesta en Unidad 2 Laboratorio 2 Página 3: Comprobación de cada respuesta del cuestionario.

La búsqueda lineal hace un recorrido completo de la lista. La búsqueda binaria ahorra tiempo al hacer un recorrido parcial de la lista.

Lo único que casi todo el mundo sabe de las computadoras es que utilizan binarios: unos y ceros. La búsqueda binaria no tiene nada que ver con eso. La palabra "binario" solo significa "dos", ya sean dos dígitos o dos mitades.
  1. Escribe tus ideas Compara  el bloque de búsqueda binaria con tu código de Página 1: Adivina mi número. ¿Qué partes son iguales? ¿Qué partes son diferentes?
    búsqueda binaria para (valor) en (datos) { variables locales (bajo) (alto) (índice actual) (elemento actual) unificar fijar (bajo) a (1) fijar (alto) a (longitud de (datos)) repetir hasta que ((bajo) > (alto)) { fijar (índice actual) a (promedio de (bajo) y (alto)) #comentario: Encuentra la palabra de en medio fijar (elemento actual) a (elemento (índice actual) de (datos)) si ((elemento actual) = (valor)) { reportar (verdadero) } si no { si ((elemento actual) > (valor)) #comentario: Elimina la mitad de la lista { fijar (alto) a ((índice actual) – (1)) } sino { fijar (bajo) a ((índice actual) + (1)) } } } reportar (falso) }
      El bloque >  (así como los bloques < y = ) compara las palabras alfabéticamente:
    (zanahoria) > (plátano) reporta verdadero (manzana) > (plátano) reporta falso
  2. Comprueba si ¿"seperar" está escrito correctamente utilizando la  búsqueda binaria para buscar la palabra en la lista de  100,000 palabras (ordenadas).
  3. Prueba la búsqueda binaria con algunas palabras que sabes que están escritas correctamente y otras que sabes que están incorrectas.
  4. Ahora utiliza la búsqueda binaria  para buscar las mismas palabras en las 100,000 palabras desordenadas.
    5. AAP-2.P.2
  5. Habla con tu compañero¿Por qué funciona en una lista pero no en la otra?

El bloque contiene no puede hacer ninguna suposición sobre la lista en la que estás buscando, pero si solo estás buscando una cosa en una lista ordenada puedes utilizar la búsqueda binaria.

AAP-2.P.2

Dos cosas afectan  la posibilidad que utilices un algoritmo de búsqueda binario:

encuentra un valor encuentra muchos valores
Datos ordenados puedes usar búsqueda binaria debes usar búsqueda lineal
Datos desordenados debes usar búsqueda lineal debes usar búsqueda lineal
Si estás trabajando con listas cortas, no es tan importante el algoritmo que utilices. Es cuando se trata de muchos datos que tienes que pensar cuidadosamente sobre el algoritmo.
  1. AAP-2.P part b, AAP-2.P.2
    Para utilizar una búsqueda binaria, los datos deben ser...
    binarios
    ordenados
    desordenados
    lineales
    ¿Cuál de las siguientes preguntas se puede responder con una búsqueda binaria, suponiendo que los datos estén ordenados? Marca todas las que apliquen:
    ¿Cuál es el número de teléfono de mi amigo Rasheed?
    Dame una lista de todas las canciones de Beyoncé.
    Dime si el pan está en la lista de compras.
    ¿Quién de mi lista de contactos vive en la Gran Avenida?
  1. Construye un corrector ortográfico.
    2. Utiliza split () by (whitespace) para convertir el texto de entrada en una lista.
  2. Habla con tu compañero¿Debe tu corrector ortográfico buscar en el diccionario cada palabra del texto o buscar en el texto cada palabra del diccionario?