4. Если элемент в нижней позиции совпадает с искомым значением, процедура возвращает соответствующий индекс позиции. В противном случае возвращается значение, указывающее на то, что искомый элемент не обнаружен. Процедура dhBinarySearch, реализующая алгоритм Binary Search, представлена
б) если искомое значение больше среднего, выполняется корректировка нижней границы; в противном случае — корректировка верхней.
а) вычисляется средняя точка оставшейся части массива;
3. Пока нижняя граница меньше верхней:
2. Устанавливаются верхняя и нижняя границы поиска.
1. Задается отсортированный массив данных и значение, которое нужно найти.
В действительности не существует единственного формального алгоритма Binary Search — их множество. Реализация программы, которую вы получите, зависит оттого, кто вам ее предоставит. Приведенный в этой книге вариант алгоритма работает следующим образом:
Как работает алгоритм Binary Search?
Примечание: Если вы упустили это в рассмотренном примере, учтите сейчас: алгоритм бинарного поиска может работать только в том случае, когда исходные данные предварительно отсортированы. Если вы хотите использовать этот метод, нужно тем или иным способом обеспечить сортировку исходных данных до применения алгоритма бинарного поиска.
Если телефонная книга содержит 1000 страниц, на первом шаге вы исключите из рассмотрения 500 страниц, на втором — еще 250. Неплохо всего для двух шагов! Поскольку принцип работы алгоритма Binary Search аналогичен, становится понятно, почему он обеспечивает очень быстрый поиск в больших наборах данных: после каждой проверки отсеивается 50% возможных значений, пока вы не наткнетесь на нужное. Строго говоря, алгоритм Binary Search в общем случае выполняет только 1од2п поисков, где п — количество просматриваемых элементов. Таким образом, чтобы найти нужный элемент среди 1000 значений или убедиться, что его там нет, требуется просмотреть не более 10 элементов. (Для читателей, испытывающих сложности при работе с логарифмами, 2 в десятой степени равняется 1024, так что 1од21000 немного меньше 10.) Замечательной особенностью логарифмической зависимости является то, что при удвоении числа элементов количество операций поиска увеличивается всего на одну.
Разумный пользователь телефонной книги, конечно, откроет книгу на букве V и начнет поиск с этого места. Представьте на секунду, что телефонная книга не имеет буквенного указателя, и, чтобы определить, в каком месте книги вы находитесь, вам нужно просматривать содержимое страницы. Как в этом случае быстро отыскать Vegetarian Pizza Kitchen? Скорее всего, вы ткнете пальцем наугад где-нибудь посредине книги, увидите, что названия, начинающиеся на V, идут дальше, и отбросите все, что находится до положения вашего пальца. Затем вы проверите среднюю страницу второй половины книги и определите, в какой половине оставшейся части книги находятся слова на букву V. Продолжая этот процесс, вы будете делить книгу на все меньшие и меньшие части, пока, наконец, не найдете нужной записи.
Представьте себе, что вы взяли телефонную книгу и намереваетесь отыскать телефон местного ресторана вегетарианской кухни Vegetarian Pizza Kitchen. Можно, конечно, начиная с первого названия в книге, двигаться по списку, рассматривая каждую позицию. Это отнимет у вас уйму времени, учитывая то, что в книге, скорее всего, сотни тысяч телефонов, а вам нужно пройти весь список до буквы V.
Почему применяется алгоритм Binary Search?
При наличии отсортированных данных вам, вероятно, потребуется осуществлять поиск определенного элемента в массиве данных. Как и сортировка, поиск является одной из важнейших операций обработки данных, и мы не ставим перед собой цели подробно осветить этот вопрос. С другой стороны, вы не найдете столько алгоритмов для поиска, сколько для сортировки. Поэтому здесь рассмотрен единственный метод поиска, но зато во всех подробностях. В данном разделе речь пойдет об алгоритме бинарного поиска Binary Search и о том, как его использовать для данных, хранящихся в массиве.
Последние добавленные новости
Навигация по предметам
Поиск в библиотеке
У нас Вы найдете много книг, лабораторных, курсовиков, учебных пособий, лекций, готовых шпор и много другого добра..
Самая домашняя библиотека - SDB.SU - это бесплатная электронная библиотека для программиста
Страница 5. Часть 5 - Программирование в Microsoft Office - К. Гетц, М. Джилберт » Самая домашняя библиотека - книги, лабораторные, курсовики, учебные пособия, лекции, исходники, шпоры - все для программиста и не только..
