Microsoft visual c++ 2008. Урок 13. Метод двоичного (бинарного) поиска. |
Автор megabax | ||
08.12.2011 г. | ||
Microsoft visual c++ 2008. Урок 13. Метод двоичного (бинарного) поиска.Предположим, у нас есть отсортированный массив. Если нам надо найти в этом массиве элемент, то мы можем искать не тупым перебором, а написать гораздо более рациональный алгоритм (это важно, когда у нас массив очень большой) - алгоритм бинарного поиска. Суть его в том, что мы условно разбиваем массив на две половинки, определяем в какой из половинок должен находиться этот элемент (методом сравнения, элементы то расположены по порядку!), затем найденную половинку делим точно так же на две части и продолжаем поиск уже в ней. И так до тех пор, пока не найдем элемент. Эффект этого метода рассмотрим на примере: пусть у нас в массиве 1 миллион элементов. Что бы найти искомый методом перебора, нам надо перебрать максимум миллион элементов. А если воспользоваться методом бинарного поиска? То нам надо будет перебрать максимум 20 элементов (всего то! чувствуете разницу?), поскольку 220 это как раз примерно1 миллион. А теперь давайте реализуем этот алгоритм на С++:
Вот протокол работы программы: Скриншоты, помеченные знаком *, являются цитатами и иллюстрациями программного продукта "Microsoft Visual C++ Express Edition", авторское право на который принадлежит корпорации Microsoft..
|
||
Последнее обновление ( 21.09.2013 г. ) |
« След. | Пред. » |
---|