Наткнулась на leetcode на задачку с нахождением квадратного корня из неотрицального числа.
Кажется, что для решения такой задачки отлично подходит бинарный поиск, который по итогу даст нам логарифмическую временную сложность.
Итак, условие задачи здесь: https://leetcode.com/problems/sqrtx/description/
Но прежде чем приступить к решению, пройдемся по теории, что такое бинарный поиск и как его использовать.
Бинарный поиск - это поисковый алгоритм, который позволяет найти элемент в отсортированном массиве с логарифмической сложностью. Массив делится пополам, искомый элемент сравнивается с серединой массива, если искомый элемент больше, то поиск переходит в правую часть массива, и наоборот. После каждого перехода в правую или левую часть будет происходить сравнение серединного элемента с искомым до тех пор, пока он не будет найден.
Акцентирую внимание еще раз: массив должен быть отсортирован по возрастанию.
Если массив не отсортирован, то сортировка потребует минимум O(log n * n) временной сложности, что нужно учитывать.
Поэтому, если массив небольшой и неупорядоченный, то, скорее всего, лучше будет линейный поиск со сложностью O(n).
Итак, теперь вернемся к нашей задачке. Нужно найти квадратный корень из неотрицательного числа, где само число может быть любым от 0 до 231 - 1. Использовать встроенные функции при этом нельзя, так что return (int) Math.sqrt(x) не подойдет (хотя leetcode ее примет). Если корень из числа извлекается с остатком, например, корень из 8 это 2.82842…, то нужно округлить в меньшую сторону до целого, т.е. в данном случае до 2.
Начнем, по порядку, ограничив краевые случаи. Так, если х = 0, то можно сразу вернуть 0.
if (x == 0) {
return 0;
}Дальше зададим границы, левую и правую. Левая граница в данном случае - это 1, а правая само число Х. Также нам понадобиться переменная, в которую мы запишем результат:
int left = 1;
int right = x;
int result = 0;Мы будем выполнять поиск нужного нам элемента, пока левая граница (left) будет меньше или равна правой (right), если левая граница станет больше, то значит результат уже был найден и нужно его возвращать.
while (left <= right) {
//тут будет алгоритм
}Внутри самого цикла while мы будем двигать границы, согласна правилу выше. Сначала найдем середину:
while (left <= right) {
int mid = left + (right - left) / 2;
...
} Если значение серединного элемента больше, чем заданное число деленное на серединный элемент, то надо двигать правую границу, иначе левую, и записывать промежуточный результат:
while (left <= right) {
int mid = left + (right - left) / 2;
if (mid > x / mid) {
right = mid - 1;
} else {
left = mid + 1;
result = mid;
}
}Допустим, заданное число - это 18. Тогда left = 1, right = 18, заходим в цикл, так как 1 < 18 (left <=right), находим mid = 1 + (18 - 1) / 2 = 9. Проверяем условие: 9 > 18 / 9, поэтому двигаем правую границу влево: right = 9 - 1 = 8.
Снова проверяем условие 1 < 8 (left <=right), входим в цикл, находим середину: mid = 1 + (8 - 1) / 2 = 4. Рассчитываем x / mid - это 18 / 4 ≈ 4, значит mid = x / mid ( 4 ≈ 18 / 4 ), значит left = 5, result = 4 (подвинули границы вправо)
Так как условие, left <= right все еще выполняется, мы снова зайдем в цикл (хотя на самом деле мы уже нашли нужный result для нашего конкретного примера), снова рассчитаем mid = 5 + (8 - 5) / 2 ≈ 6, вычислим x / mid = 18 / 6 = 3, попадем в условие mid > x / mid, так как 6 > 3, пересчитаем right = 6 - 1 = 5. Снова зайдем в цикл, и выйдем уже на следующем пересчете right, когда right будет равно 4, а left останется без изменений. После этого будет возвращен результат.
Фиксируем полный метод для решения задачи:
public int mySqrt(int x) {
if (x == 0) {
return 0;
}
int left = 1;
int right = x;
int result = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (mid > x / mid) {
right = mid - 1;
} else if {
left = mid + 1;
result = mid;
}
}
return result;
}Вот так можно использовать бинарный поиск для нахождения квадратного корня из числа. Если еще хотите попрактиковаться, то вот еще задачка уровня «Easy», где применяется тот же подход:
https://leetcode.com/problems/search-insert-position/description/
Комментарии (25)
wataru
29.07.2024 12:08+1Важно указать, что в условии просят решить задачу без использования встроенных функций извлечения корня или возведения в степень.
Теперь вот вопрос: у вас в статье написано, что бинарный поиск работает на упорядоченном массиве. Но в задаче у вас никакого массива вообще нет. Как так?
Ну и маленькое замечание
else if (mid <= x / mid)- тут условие не нужно, ведь это ветка elsе в проверке обратного условия. Оно тут всегда выполняется.
akozyrenko Автор
29.07.2024 12:08Массива тут как таковой неочевиден, но фактически он есть. Ведь числа, которыми мы огибаем границы, как раз выстраиваются в упорядоченный массив (от 1 до Х)
С остальными замечаниями согласна, поправила/добавила:)
wataru
29.07.2024 12:08+1Массива тут как таковой неочевиден, но фактически он есть.
Я к тому, что этот момент стоит расписать поподробнее. Что на самом деле у вас есть мнимый массив, где по индексу i стоит число i^2. Ясно, что если найти в этом массиве самое большое число, не превосходящее x, то его индекс и будет ответом на задачу. Для большей ясности стоило бы задачу еще и формализовать (вроде:
) Тогда понятно, что мы ищем в массиве.Вместо хранения массива его значения можно просто вычислять, когда они нужны, m*m в коде - это фактически array[m]. Кстати, хорошо бы описать, почему вы вместо m*m > x используете m > x/m - это же чтобы избежать переполнения, да?
И вообще, в статье много объяснения "что", и почти нет объяснения "почему". Поэтому для людей не имеющих опыт применения дихотомии для решения подобных задач уже, ваша статья мало полезна, ибо это какая-то черная магия получается. Вот так вот двигаем границы, а почему, откуда, где тут вообще квадратный корень - этого из вашей статьи не понять.
akozyrenko Автор
29.07.2024 12:08Спасибо за фидбек.
Согласна, что этот момент стоило бы расписать подробнее. Возьму на заметку для следующих статей.
wataru
29.07.2024 12:08Еще тонкий момент, а почему x=0 у вас крайний случай? Почему нельзя просто сделать l=0?
akozyrenko Автор
29.07.2024 12:08Если вы сделаете left = 0, то словите ArithmeticException для х от 0 до 3 включительно
wataru
29.07.2024 12:08+1Только потому что вы решили делить x на m в усорвии, вместо логичного m*m. И об этом надо было написать в тексте статьи. И вообще, этот частный случай - он из-за вот той вот детали реализации, поэтому его стоило бы рассмотреть в конце, а не начинать с него повествование.
vadimr
29.07.2024 12:08Идея понятна, но пример выбран неудачно. Быстрое вычисление квадратного корня – это очень хорошо исследованная задача, и её можно решить гораздо быстрее бинарного поиска.
Например, вот тут люди обсуждают эту тему.
GeXoGeN
29.07.2024 12:08да с примером кажется вообще пофиг. ведь этим способом можно искать корни чуть ли не любого уравнения вообще.
vadimr
29.07.2024 12:08Ну да, известный способ поиска корня методом половинного деления. Есть нюансы, конечно, но в целом рабочий.
GeXoGeN
29.07.2024 12:08+1настолько известный, что проходится в программе обычного технического ВУЗа даже не по IT-специальностям. по-моему даже ещё какие-то проходили, но этот лучше всего запомнился, как самый очевидный. там больше всего сложностей, когда корней больше чем один.
GeXoGeN
Правой границей можно сразу делать Х/2. и ещё, наверное, умножение будет работать быстрее деления вот тут:
akozyrenko Автор
Нельзя, потому что если х = 1, в ответе вы получите 0, что неверно.
GeXoGeN
ну для х = 0 частный случай же Вы определили, можно и для х = 1 определить или даже скорее для 0<x<4, чтобы вообще быть точным, если вдруг захочется в будущем не только целочисленные корни искать
akozyrenko Автор
зачем определять 4 таких случая, загрязняя код, если все, кроме того, что обозначено с 0, и так отсеется на первом шаге цикла. Мы ничего не выиграем по скорости, а лишь только накрутим код.
GeXoGeN
не ещё четыре, а ещё один. раз в задаче требуется округление путём отбрасывания дробной части, то при 0<Х<4 ответ будет равен 1, можно сразу его вернуть. либо если вдруг мы захотели вычислять дробную часть тоже, то в этой ветке кода можно оставить правой границей Х и дальше просто продолжить выполнять тот же алгоритм.
Sigest
Умножение может и будет работать быстрее, я так понимаю вы предлагаете (mid*mid>x)? Там при больших числах mid (тест кейс с leetcode x=2147395599) будет переполнение и в бесконечный цикл уйдет, так как проверка будет работать неправильно. А если заморачиваться с BigInt, то может ну его нафик, пусть с делением работает
GeXoGeN
Mid*mid ни при каких условиях не будет больше максимального значения X. Я же не просто так написал, что начальную правую границу нужно сделать равной Х/2.Чето я наврал тут. Не читайте. Можно использовать uint.
GeXoGeN
Блин. Uint тоже не хватит. Всё, сдаюсь, посыпаю голову пеплом.
wataru
Там не надо BigInt, достаточно long long.
Alexandroppolus
если искать в пределах отрезка [0 ... 46340], то без переполнений уместится в int32
akozyrenko Автор
По условию задачи заданное число может быть в пределах отрезка от 0 до 2 в 31 степени - 1, поэтому mid выйдет за пределы при использовании умножения.
wataru
Но корень-то не может быть больше 46340.
akozyrenko Автор
ну, можете прогнать кейс с х = 2^31-1:), mid*mid вылетит за пределы int:)
Alexandroppolus
а вы не забыли сделать
int right = min(x,46340);?