Лек. Бинарный поиск. Бинарный поиск производится в упорядоченном массиве
 Скачать 44.07 Kb.
|
|
Бинарный поиск производится в упорядоченном массиве. При бинарном поиске искомый ключ сравнивается с ключом среднего элемента в массиве. Если они равны, то поиск успешен. В противном случае поиск осуществляется аналогично в левой или правой частях массива. Алгоритм может быть определен в рекурсивной и нерекурсивной формах. Бинарный поиск также называют поиском методом деления отрезка пополам или дихотомии. Количество шагов поиска определится как log2n↑, где n-количество элементов, ↑ — округление в большую сторону до ближайшего целого числа. На каждом шаге осуществляется поиск середины отрезка по формуле mid = (left + right)/2 Если искомый элемент равен элементу с индексом mid, поиск завершается. В случае если искомый элемент меньше элемента с индексом mid, на место mid перемещается правая граница рассматриваемого отрезка, в противном случае — левая граница.   Подготовка. Перед началом поиска устанавливаем левую и правую границы массива: left = 0, right = 19 Шаг 1. Ищем индекс середины массива (округляем в меньшую сторону): mid = (19+0)/2=9 Сравниваем значение по этому индексу с искомым: 69 < 82 Сдвигаем левую границу: left = mid = 9 Шаг 2. Ищем индекс середины массива (округляем в меньшую сторону): mid = (9+19)/2=14 Сравниваем значение по этому индексу с искомым: 84 > 82 Сдвигаем правую границу: right = mid = 14 Шаг 3. Ищем индекс середины массива (округляем в меньшую сторону): mid = (9+14)/2=11 Сравниваем значение по этому индексу с искомым: 78 < 82 Сдвигаем левую границу: left = mid = 11 Шаг 4. Ищем индекс середины массива (округляем в меньшую сторону): mid = (11+14)/2=12 Сравниваем значение по этому индексу с искомым: 80 < 82 Сдвигаем левую границу: left = mid = 12 Шаг 5. Ищем индекс середины массива (округляем в меньшую сторону): mid = (12+14)/2=13 Сравниваем значение по этому индексу с искомым: 82 = 82 Некто загадал число от 1 до 100. Требуется отгадать загаданное число с помощью вопросов вида «Загаданное число больше числа X?» Решение Положим отрезок поиска решения [L, R] равным [1, 100], т.е. L=1 и R=100. Далее, перед каждым вопросом будем вычислять X как середину отрезка [L, R], т.е. X = (L+R) div 2. В случае ответа «Да» задача сводится к поиску решения на отрезке [X+1, R] и мы полагаем, что L = X+1. В случае ответа «Нет» поиск загаданного числа следует продолжить на отрезке [L, X], для чего полагаем, что R = X. Описанные выше действия следует продолжать до тех пор, пока L < R. По завершению алгоритма мы найдем ответ (он равен L и R). Следует отметить, что мы выполним не более 7 вопросов, т.к. 27 > 100. Задача 1. Улучшение успеваемости Ограничение по времени: 1 секунда Ограничение по памяти: 512 мегабайт В лицее на уроках информатики ответы учеников оцениваются целым числом баллов от 2 до 5. Итоговая оценка по информатике выставляется как среднее арифметическое оценок на всех уроках, округленное до ближайшего целого числа. Если среднее значение находится ровно посередине между двумя целыми числами, то оценка округляется вверх. Примеры округления оценок приведены в таблице.  Все ученики лицея стремятся получить итоговую оценку по информатике не ниже 4 баллов. К сожалению, один из учеников получил на уроках a двоек, b троек и c четверок. Теперь он планирует получить несколько пятерок, причем хочет, чтобы итоговая оценка была не меньше 4 баллов. Ему надо понять, какое минимальное количество пятерок ему необходимо получить, чтобы добиться своей цели. Требуется написать программу, которая по заданным целым неотрицательные числам a, b и c определяет минимальное количество пятерок, которое необходимо получить ученику, чтобы его итоговая оценка по информатике была не меньше 4 баллов. Решение: Пусть ученик получит x оценок в 5 баллов. Тогда общее число оценок будет равно (a + b + c + x), а средняя оценка будет равна (2a + 3b + 4c + 5x) / (a + b + c + x). По условию задачи должно выполняться условие (2a + 3b + 4c + 5x) / (a + b + c + x) ≥ 3.5. Каждая дополнительная оценка в 5 баллов увеличивает среднюю оценку, следовательно для поиска минимального значения x, при котором среднее значение не меньше 3.5 можно применить двоичный поиск. |