Иллюстрированный самоучитель по Delphi 7 для начинающих

Метод бинарного поиска

На практике довольно часто производится поиск в массиве, элементы которого упорядочены по некоторому критерию (такие массивы называются упорядоченными). Например, массив фамилий, как правило, упорядочен по алфавиту, массив данных о погоде – по датам наблюдений. В случае, если массив упорядочен, то применяют другие, более эффективные по сравнению с методом простого перебора алгоритмы, один из которых – метод бинарного поиска.

Пусть есть упорядоченный по возрастанию массив целых чисел. Нужно определить, содержит ли этот массив некоторое число (образец).

Метод (алгоритм) бинарного поиска реализуется следующим образом:

  1. Сначала образец сравнивается со средним (по номеру) элементом массива (рис. 5.10, а).
    • Если образец равен среднему элементу, то задача решена.
    • Если образец больше среднего элемента, то это значит, что искомый элемент расположен ниже среднего элемента (между элементами с номерами sred+1 и niz), и за новое значение verb принимается sred+1, а значение niz не меняется (рис. 5.10, б).
    • Если образец меньше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента (между элементами с номерами verh и sred-1), и за новое значение niz принимается sred-1, а значение verh не меняется (рис. 5.10, в).

Иллюстрированный самоучитель по Delphi 7 для начинающих › Массивы › Метод бинарного поиска
Рис. 5.10, а) Выбор среднего элемента массива при бинарном поиске

Иллюстрированный самоучитель по Delphi 7 для начинающих › Массивы › Метод бинарного поиска
Рис. 5.10, б)

Иллюстрированный самоучитель по Delphi 7 для начинающих › Массивы › Метод бинарного поиска
Рис. 5.10, в)

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.