Метод половинного деления

Определения и обозначения

Метод половинного деления — способ постепенно находить нужное число, каждый раз оставляя половину возможного диапазона. Представь, что ищешь число в большом промежутке и можешь сравнивать его с выбранными числами. Проверка середины сразу убирает примерно половину вариантов. Поэтому такой способ обычно быстрее, чем проверять числа по одному.

Интервал поиска — промежуток, в котором находится искомое число. Его границы показывают, между какими значениями нужно искать ответ. Например, если число находится между 2 и 12, то начальный интервал — от 2 до 12. Эти границы нужны, чтобы вычислить середину и понимать, какую часть можно отбросить.

Середина интервала — число, равноудалённое от его границ; её находят как полусумму границ. Для границ 2 и 12 середина равна (2 + 12) ÷ 2 = 7. Проверяют именно её, потому что она делит диапазон на две равные части. Если середина выбрана неверно, поиск может стать неточным.

Точность поиска — условие остановки: например, достаточно, чтобы ширина оставшегося интервала стала меньше заданной величины. Ширина — это разность между верхней и нижней границами. Если нужна точность до 0,1, можно остановиться, когда ширина станет меньше 0,1. Точность нужна, чтобы понимать, когда приближённый ответ уже достаточно близок к искомому.

Как это устроено

Сначала выбирают интервал, про который известно, что искомое число находится внутри него. Это не просто удобство: без подходящих границ нельзя понять, какие значения можно отбросить. Например, если число больше 0 и меньше 100, эти значения становятся началом поиска. Чем точнее задан интервал, тем меньше шагов обычно потребуется.

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

По результату проверки выбирают половину, где может находиться ответ, а другую отбрасывают. Так можно делать только потому, что сравнение или условие позволяют определить, с какой стороны от середины искать дальше. Например, если искомое число больше середины, значения слева от неё уже не подходят. После выбора половины её границы становятся новыми границами интервала.

Деление повторяют с новым интервалом, каждый раз снова вычисляя середину. Ширина промежутка уменьшается вдвое, потому что из двух равных частей оставляют одну. Если исходная ширина равна 20, после первого шага она станет 10, после второго — 5, затем — 2,5. Поэтому даже большой диапазон быстро становится узким, хотя точное число может ещё не быть найдено.

Поиск прекращают, когда получили точное значение или достигли заданной точности. Если проверка дала точный ответ, дальнейшие шаги не нужны. Если условие остановки связано с шириной, её вычисляют как разность границ и сравнивают с требуемой величиной. Когда точного ответа нет, середина оставшегося интервала подходит как приближённый ответ: она находится внутри него и не дальше границ, чем другие крайние значения.

Шаги метода половинного деления

Пользуйся таблицей сверху вниз: на каждом повторе поиска снова находи середину уже нового интервала. После проверки обязательно запиши обновлённые границы, иначе следующий шаг начнётся не с того места. Перед ответом проверь, что условие остановки действительно выполнено.

Разбор задач

Задумано целое число от 1 до 16. Найдите его за минимальное число вопросов, на которые можно ответить «больше», «меньше» или «равно».

Чтобы потратить как можно меньше вопросов, нужно каждый раз делить оставшийся диапазон примерно пополам. Первый вопрос зададим про 8: тогда числа отсекаются на две части, а ответ «равно» сразу завершает поиск. Если число больше или меньше, тот же приём применяем к оставшейся части.

1. Спросим: «Задумано число 8?» Если ответ «равно», поиск закончен; если «меньше» или «больше», останется соответственно диапазон от 1 до 7 или от 9 до 16.
2. В оставшемся диапазоне спросим о его середине. Например, для чисел от 1 до 7 проверим 4, а затем по ответу оставим числа ниже или выше неё.
3. Повторим проверку середины. Каждый вопрос уменьшает количество возможных чисел примерно вдвое, пока ответ не окажется угаданным.

При таком способе достаточно не более четырёх вопросов: после каждого вопроса число возможных вариантов сокращается примерно вдвое, а четыре деления позволяют различить до 16 вариантов. Ответ — искать середины оставшегося диапазона; если ответ «равно» не получен раньше, после четвёртого вопроса число можно определить. Последний диапазон важно делить так, чтобы варианты по обе стороны середины были как можно более равными.

Нужно найти число от 0 до 100 с точностью до 1. Покажите первые шаги поиска, если на вопрос о середине выясняется, что искомое число больше неё.

Начальный интервал имеет границы 0 и 100, а его середина равна 50. По условию проверки ответ больше середины, значит, нижнюю половину отбрасываем. Для наглядности будем продолжать именно тот же ход: на каждом шаге искомое число оказывается больше проверяемой середины.

1. Проверяем 50. Ответ больше, поэтому новые границы — 50 и 100, а ширина стала 50.
2. Середина нового интервала — (50 + 100) ÷ 2 = 75. Если ответ больше 75, оставляем интервал от 75 до 100.
3. Теперь середина равна (75 + 100) ÷ 2 = 87,5. При ответе «больше» оставляем промежуток от 87,5 до 100.

Дальше каждый раз вычисляем середину обновлённых границ и выбираем сторону по результату сравнения. Остановиться нужно, когда ширина интервала станет меньше 1 либо найдено точное значение. Ответ при заданной точности можно взять равным середине последнего интервала; если на каком-то шаге число окажется меньше середины, верхнюю границу нужно будет заменить этой серединой.

Искомое число находится между 0 и 10, а для проверки числа доступно условие: число в квадрате меньше 30 или нет. Найдите значение с точностью до 0,1.

Здесь нельзя спросить, больше ли проверяемая середина самого ответа. Вместо этого узнаём, меньше ли её квадрат 30. При положительных числах квадрат растёт вместе с числом: если квадрат уже не меньше 30, подходящие значения находятся ниже проверенной середины. Если квадрат меньше 30, ответ находится выше неё.

1. Середина интервала от 0 до 10 равна 5. Проверяем: 5² = 25, а 25 меньше 30, поэтому оставляем верхнюю половину — от 5 до 10.
2. Новая середина равна 7,5. Так как 7,5² = 56,25 и это не меньше 30, оставляем нижнюю половину — от 5 до 7,5.
3. На следующих шагах снова проверяем квадрат середины и выбираем половину по тому же правилу. Продолжаем, пока ширина интервала не станет меньше 0,1.

Для примера, следующая середина равна 6,25; её квадрат 39,0625 больше 30, поэтому верхнюю границу меняем на 6,25. После дальнейших проверок получим интервал, ширина которого меньше 0,1, а значение будет около 5,5. Ответ с точностью до 0,1 — примерно 5,5; правило выбора половины здесь опирается на то, что все числа интервала положительные.

Типичные ошибки

Первая ошибка — считать серединой половину одной границы, а не полусумму границ. Так бывает, когда слово «половина» понимают как деление одного числа на 2; в результате проверяют точку, которая не делит интервал пополам. Проверь вычисление по формуле: сложи обе границы и только потом раздели сумму на 2. Например, для 2 и 12 правильная середина — 7, а не 6.

Вторая ошибка — оставить половину, в которой ответа быть не может. Её допускают, если неверно связывают слова «больше» и «меньше» с направлением поиска. Перед обновлением границы ещё раз сформулируй, что означает результат проверки. Можно проверить себя на простом примере: если число больше 8, интервал ниже 8 оставлять нельзя.

Третья ошибка — не менять границы после шага. Тогда при следующем вычислении снова получится прежняя середина, и поиск не будет сужаться. После каждой проверки запиши новую нижнюю или верхнюю границу. Убедись, что новая ширина действительно вдвое меньше предыдущей.

Четвёртая ошибка — делить интервал бесконечно или остановиться без проверки точности. В первом случае непонятно, когда считать ответ готовым, а во втором он может оказаться слишком неточным. До начала поиска задай условие остановки: например, точное попадание или ширина меньше 0,1. В конце вычисли ширину оставшегося интервала и сравни её с этим условием.

Связь с другими темами

Для работы методом половинного деления нужно уметь сравнивать числа, находить середину отрезка и делить пополам. Эти навыки помогают вычислять новую проверочную точку и верно выбирать границы. Метод также пригодится для эффективного поиска в упорядоченном списке: сравнение с серединой позволяет отбрасывать часть списка. Ещё его используют для приближённого нахождения числа, которое удовлетворяет заданному условию.

Что запомнить

• Начинай с интервала, содержащего искомое число.
• Проверяй середину интервала.
• После проверки оставляй только подходящую половину.
• На каждом шаге ширина интервала уменьшается вдвое.
• Заранее определи условие остановки.
• Если точного ответа нет, можно взять середину оставшегося интервала.