Почему нельзя использовать двоичный поиск в несортированном массиве?

Представьте, что вы пытаетесь найти дом на действительно длинной улице с 1000 домами. Это будущее, и мы освоили способность телепортироваться. Все, что у вас есть, - это адрес, но вы не знаете, у каких домов есть адреса. Они могут быть пронумерованы 1, 5, 9, 19, 25, 28, 37 и так далее. Города оставляют эти промежутки специально, чтобы иметь адреса, которые можно использовать, если в будущем будут построены новые дома.

Самый простой способ быстро найти дом - это телепортироваться на полпути на улице. Вы можете посмотреть адрес дома, в котором находитесь. Если вам нужен дом большего размера, то вы знаете, что это должен быть один из домов дальше по улице. Но если дом, который вы ищете, меньше, он должен быть в другом направлении.

Телепортируясь на полпути, вы вдвое сократили количество домов для поиска. В первый раз вы телепортировались на полпути к 500-му дому на улице. Но вы можете снова разрезать дома пополам, повторив этот процесс. Если номер дома, который вам нужен, больше, вы телепортируетесь в 750-й дом. Если номер дома, который вам нужен, меньше, вы телепортируетесь в 250-й дом. Вы проверяете снова и быстро начинаете сужать область, где должен быть дом.

Поскольку каждый телепорт сокращает количество домов вдвое, вы гарантированно найдете дом, который хотите, за 11 телепортов или меньше. Это намного быстрее, чем проверять все 1000 домов по очереди. Именно так работает бинарный поиск. Компьютер переходит к середине отсортированного списка, а затем проверяет, находится ли то, что он хочет, ближе к началу или концу. Он повторяет процесс, каждый раз сокращая количество, которое нужно найти, пополам.

Предполагается, что список отсортирован. Вернемся к аналогии с домом. Допустим, все дома на улице были пронумерованы случайным образом (54, 1009, 2, 4006, 57, 186, 17, ...), тогда переход на полпути не поможет. Когда вы переходите к 500-му дому, у вас нет возможности узнать, находится ли дом, который вы хотите, справа или слева, потому что он не в порядке. Единственный способ найти подходящий дом - это проверить их по одному.

Люди постоянно используют двоичный поиск. Когда мы ищем людей в телефонной книге, мы используем аналогичный процесс перелистывания ближе к тому месту, где мы думаем, а затем перелистываем на несколько страниц вперед или назад, пока не найдем нужный номер телефона. Если бы имена в телефонной книге были не по порядку или просто занесены случайным образом, было бы практически невозможно найти то, что вы ищете.