Презентация Бинарный поиск онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Бинарный поиск абсолютно бесплатно. Урок-презентация на эту тему содержит всего 12 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:12 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:598.90 kB
- Просмотров:87
- Скачиваний:2
- Автор:неизвестен
Слайды и текст к этой презентации:
№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);
}
}
№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++).
Вирт Н. Алгоритмы + структуры данных = программы.
Скачать все slide презентации Бинарный поиск одним архивом:
