¿Por qué no se puede utilizar la búsqueda binaria en una matriz sin clasificar?

Imagina que estás tratando de encontrar una casa en una calle muy larga con 1000 casas. Este es el futuro y hemos dominado la capacidad de teletransportarnos. Todo lo que tiene es la dirección de la calle, pero no sabe qué casas tienen direcciones. Pueden estar numerados 1, 5, 9, 19, 25, 28, 37, etc. Las ciudades dejan estos huecos a propósito para tener direcciones que usar si se construyen nuevas casas más adelante.

La forma más fácil de encontrar la casa rápidamente sería teletransportarse al punto medio de la calle. Podrías mirar la dirección de la casa en la que te encuentras. Si la casa que desea es un número mayor, entonces sabe que debe ser una de las casas más abajo en la calle. Pero si la casa que busca es un número menor, debe estar en la otra dirección.

Al teletransportarse a la mitad del camino, ha reducido a la mitad el número de casas para buscar. La primera vez que te teletransportaste a mitad de camino a la casa número 500 en la calle. Pero puedes volver a cortar las casas por la mitad repitiendo el proceso. Si el número de casa que desea es mayor, se teletransporta a la casa 750. Si el número de casa que desea es menor, se teletransporta a la casa número 250. Verifica de nuevo y rápidamente comienza a reducir dónde debe estar la casa.

Dado que cada teletransporte reduce el número de casas a la mitad, tiene la garantía de encontrar la casa que desea en 11 teletransportes o menos. Esto es mucho más rápido que verificar las 1000 casas una a la vez. Así es exactamente como funciona una búsqueda binaria. La computadora va al punto medio de una lista ordenada y luego verifica si lo que quiere está más cerca del principio o del final. Repite el proceso, cada vez cortando a la mitad cuánto necesita buscarse.

Esto supone que la lista está ordenada. Volvamos a la analogía de la casa. Digamos que todas las casas de la calle están numeradas al azar (54, 1009, 2, 4006, 57, 186, 17, ...) y luego ir al punto medio no ayudaría. Cuando vas a la casa número 500, no tienes forma de saber si la casa que quieres está a la derecha oa la izquierda porque no están en orden. La única forma de encontrar la casa adecuada es comprobarlos uno por uno.

Las búsquedas binarias son utilizadas hasta cierto punto por la gente todo el tiempo. Cuando buscamos personas en un directorio telefónico, usamos un proceso similar de pasar las páginas cerca de donde pensamos que podría estar y luego pasar algunas páginas hacia adelante o hacia atrás hasta encontrar el número de teléfono correcto. Si los nombres en la guía telefónica estuvieran desordenados o simplemente se pusieran al azar, sería prácticamente imposible encontrar lo que está buscando.