Как работает двоичный поиск в упорядоченных массивах?

Двоичный поиск — это алгоритм поиска элемента в отсортированном массиве, который последовательно делит диапазон поиска пополам для быстрого нахождения искомого значения. 1

Алгоритм работы: 1

1. Инициализация границ поиска. 1 Устанавливаются начальные значения индексов — низший (low) и высший (high). 1
2. Определение среднего элемента. 1 Вычисляется средний индекс. 1
3. Сравнение со средним элементом: 1

• Если значение по индексу mid равно ключу, то поиск завершается. 1
• Если ключ меньше значения в mid, продолжается поиск в левой половине массива. 1
• Если ключ больше значения в mid, продолжается поиск в правой половине массива. 1

1. Обновление границ и повтор. 1 Шаги 2–3 повторяются, пока низший индекс не превысит высший. 1

Пример работы: 3

Есть отсортированный массив чисел: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. 3 Нужно найти в нём число 5. 3

1. Сначала берётся средний элемент массива, в данном случае это число 6. 3
2. Затем сравнивается с искомым значением. 3 Так как 6 больше 5, сужается область нахождения до левой половины массива: [1, 2, 3, 4, 5]. 3
3. Снова берётся средний элемент, в данном случае это число 3, и сравнивается с искомым значением. 3 Так как 3 меньше 5, сужается область нахождения до правой половины массива: [4, 5]. 3
4. Процесс продолжается до тех пор, пока не будет найден искомый элемент или пока не останется только один элемент для сравнения. 3

В случае, если искомый элемент не найден, возвращается информация об отсутствии такого элемента в массиве. 3