Наткнулась на 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/
Комментарии (33)
wataru
29.07.2024 12:08+2Важно указать, что в условии просят решить задачу без использования встроенных функций извлечения корня или возведения в степень.
Теперь вот вопрос: у вас в статье написано, что бинарный поиск работает на упорядоченном массиве. Но в задаче у вас никакого массива вообще нет. Как так?
Ну и маленькое замечание
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-специальностям. по-моему даже ещё какие-то проходили, но этот лучше всего запомнился, как самый очевидный. там больше всего сложностей, когда корней больше чем один.
NikolayTheSquid
29.07.2024 12:08+2Можно вычислять серединным поиском значение любой непрерывной мотонной функции (логарифма, экпоненты и т.д.). Казалось бы, решение подобных простейших задач не заслуживает размазывания на целую статью. Стыдно, но такой уж нынче Хабр победивших продактов, эйчаров и прочих чертей, не знакомых со школьными истинами.
GeXoGeN
Правой границей можно сразу делать Х/2. и ещё, наверное, умножение будет работать быстрее деления вот тут:
akozyrenko Автор
Нельзя, потому что если х = 1, в ответе вы получите 0, что неверно.
GeXoGeN
ну для х = 0 частный случай же Вы определили, можно и для х = 1 определить или даже скорее для 0<x<4, чтобы вообще быть точным, если вдруг захочется в будущем не только целочисленные корни искать
akozyrenko Автор
зачем определять 4 таких случая, загрязняя код, если все, кроме того, что обозначено с 0, и так отсеется на первом шаге цикла. Мы ничего не выиграем по скорости, а лишь только накрутим код.
GeXoGeN
не ещё четыре, а ещё один. раз в задаче требуется округление путём отбрасывания дробной части, то при 0<Х<4 ответ будет равен 1, можно сразу его вернуть. либо если вдруг мы захотели вычислять дробную часть тоже, то в этой ветке кода можно оставить правой границей Х и дальше просто продолжить выполнять тот же алгоритм.
Proscrito
Обработка частных и граничных случаев это не загрязнение, а очистка кода. Объем и чистота не синонимы.
Sigest
Умножение может и будет работать быстрее, я так понимаю вы предлагаете (mid*mid>x)? Там при больших числах mid (тест кейс с leetcode x=2147395599) будет переполнение и в бесконечный цикл уйдет, так как проверка будет работать неправильно. А если заморачиваться с BigInt, то может ну его нафик, пусть с делением работает
GeXoGeN
Mid*mid ни при каких условиях не будет больше максимального значения X. Я же не просто так написал, что начальную правую границу нужно сделать равной Х/2.Чето я наврал тут. Не читайте. Можно использовать uint.
GeXoGeN
Блин. Uint тоже не хватит. Всё, сдаюсь, посыпаю голову пеплом.
wataru
Там не надо BigInt, достаточно long long.
Sigest
Мы про джаву же. Что за long long? Ну ок, пусть будет джавовский Long. Но, во-первых по условию задачи (если смотреть инициализированный код на leetcode) вход и выход имеют тип int. Ок значит внутри алгоритма мы туда сюда преобразовываем из int в long и назад когда возвращаем результат. Во-вторых long-овая математика работает дольше int-овой. По сути мы ничего не выигрываем. Конкретно в данном случае.
wataru
Целых 2 перобразования. На самом деле они вообще бесплатные для процессора. Ему без разницы, загрузить 64 бита в регистр EAX или 32 бита в AX.
Не правда. Уже очень давно процессоры 64-битные. Там операции с Long и Int занимают одинаковое время.
Единственный минус Long - это работа с памятью. Если у вас большой массив данных, то работа с Int будет быстрее из-за более плотного расположения в памяти и более частого попадания в кеш при чтении. Но наша задача этим не страдает.
Выигрываем то, что умножение действительно быстрее деления. Довольно сильно.
Sigest
Не буду спорить. Скорее всего вы правы. Либо они одинаковы по скорости, либо очень не существенно. Я больше ориентировался не на битность процессора, а на его кеш. В голове очень давно , еще при изучении многопоточности, отложилось что в операциях с long на уровне процессора происходят оптимизации и в несинхронизированном коде (точнее без volatile) вполне реальна ситуация когда в одном потоке long переменная обновилась, а в другом потоке первые 32бита прочитались верно, а вторые закешировались и мы имеем вполне легальное, но неверное значение. Вот поэтому у меня такая мысль про long и закрепилась, что математика тут сложнее, чем с int
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);?akozyrenko Автор
А как вы определили 46340 на этапе, когда мы записываем значение right, без использования встроенных функций?
Alexandroppolus
Посчитал на калькуляторе) Условие гарантирует, что прилетит число от 0 до 2^31-1, благодаря чему я могу с чистой совестью захардкодить signed int32 для типа параметра, и (что то же самое) число 46340.
Рамки выглядят искусственно, но от них не уйти. Этот ваш O(ln N) по факту справедлив только если N не больше какой-то константы, чтобы числа и операции с ними стоили O(1). Из-за чего весь алгоритм формально обесценивается до О(1). А для произвольной верхней границы N у нас будет длинная арифметика, числа длиной L = ln(N), стоимость умножения O(L * ln(L)), итого O(ln(N)^2 * ln(ln(N))) на всё про всё, если я нигде не ошибся. Тогда можно не заморачиваться на переполнения и ничего не хардкодить.
VBDUnit
Есть же специальная операция int32 × int32 = int64. Как раз для защиты от переполнений