Как работает бинарный поиск?

Делишь массив пополам, сравниваешь середину с искомым, отбрасываешь ненужную половину, повторяешь. Пример: ищешь 9 в 1, 3, 5, 7, 9, 11, 13. Середина 7, девять больше, берёшь правую часть 9, 11, 13. Середина теперь 11, девять меньше, остаётся 9. Три шага вместо перебора всех семи чисел подряд.

Бинарный поиск ищет число в отсортированном массиве, каждый раз отбрасывая половину оставшихся вариантов. Возьми массив 1, 3, 5, 7, 9, 11, 13 и найди в нём число 9. Сначала смотришь на середину: это 7. Девять больше семи, значит искомое число точно правее, и всю левую половину вместе с семёркой можно выбросить из рассмотрения. Остаётся 9, 11, 13, середина теперь 11. Девять меньше одиннадцати, отбрасываем правую часть. Остаётся одно число, 9, это и есть ответ, найден за три сравнения вместо семи при обычном переборе по порядку. Условие про отсортированность важно именно поэтому: только на упорядоченных данных можно уверенно сказать, в какой половине искать дальше, не проверяя вторую.

• Массив обязательно отсортирован.
• Сравниваем искомое с серединой.
• Отбрасываем половину, где числа точно не подходят.
• Повторяем, пока не найдём или не кончится массив.