Бинарный поиск - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Бинарный поиск. Доклад-сообщение содержит 12 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Бинарный поиск

Слайд 2

Описание слайда:

ОПРЕДЕЛЕНИЕ

Слайд 3

Описание слайда:

Алгоритм Проверить, что искомое значение не выходит за границы области поиска; Найти середину области поиска; Если искомое значение больше, чем значение в середине области, то повторяем поиск в области от середины до наибольшего значения области, иначе – от наименьшего до середины.

Слайд 4

Описание слайда:

Слайд 5

$ПРИМЕР РЕАЛИЗАЦИИ int binary_search (int value, int *array, int *first, int *last){ if ((value>*(last))||(value<*first)) return -1; else if (last-first==1) { if (*first==value) return array-first; else if (*(last)==value) return last-array; else return -1; } else { unsigned int mid = (last - first) / 2; if (value > *(first + mid)) return binary_search(value, array, first + mid, last); else return binary_search(value, array, first, last - mid); } }$

Описание слайда:

ПРИМЕР РЕАЛИЗАЦИИ int binary_search (int value, int *array, int *first, int *last){ if ((value>*(last))||(value<*first)) return -1; else if (last-first==1) { if (*first==value) return array-first; else if (*(last)==value) return last-array; else return -1; } else { unsigned int mid = (last - first) / 2; if (value > *(first + mid)) return binary_search(value, array, first + mid, last); else return binary_search(value, array, first, last - mid); } }

Слайд 6

Описание слайда:

ТИПИЧНЫЕ ОШИБКИ first+last вызывает выход за границы диапазона используемого типа данных. Решается использованием указателей или итераторов. Ошибки на единицу. Ищется не первое/последнее значение.

Слайд 7

Описание слайда:

STL bool binary_search – возвращает истину, если искомый элемент встречается в массиве и ложь в противном случае. binary_search(array_100,array_100+100,63);

Слайд 8

Описание слайда:

СКОРОСТЬ РАБОТЫ

Слайд 9

Описание слайда:

Замечания Значение mid – не обязательно середина массива. Оно определяется как граница раздела двух областей поиска – той, в которой будет продолжен поиск, и той, которая будет отброшена. Большинство задач на бинарный поиск подразумевают именно правильное определение mid. Единого алгоритма для данного алгоритма не существует. В каждом случае mid определяется только на основе анализа задачи.

Слайд 10

Описание слайда:

Замечания Бинарный поиск работает с любыми структурами данных, которые расположены в памяти последовательно и отсортированы. В случае использования таких структур данных, как стек, очередь, дерево и т.д. бинарный поиск не работает.

Слайд 11

Описание слайда:

Замечания Бинарный поиск можно использовать для монотонных функций. Функция монотонна в том случае, если она всё время не убывает или не возрастает. Примеры – линейная, кубическая, логарифм, экспонента.

Слайд 12

Описание слайда:

Литература Кнут, «Искусство программирования», том 3; Лафоре, «Структуры данных и алгоритмы Java» (тут хватит и знаний C++). Вирт Н. Алгоритмы + структуры данных = программы.

Теги Бинарный поиск

Похожие презентации