Comments 38
Левая граница в данном случае - это 1, а правая само число Х.
Правой границей можно сразу делать Х/2. и ещё, наверное, умножение будет работать быстрее деления вот тут:
(mid > x / mid)
Нельзя, потому что если х = 1, в ответе вы получите 0, что неверно.
ну для х = 0 частный случай же Вы определили, можно и для х = 1 определить или даже скорее для 0<x<4, чтобы вообще быть точным, если вдруг захочется в будущем не только целочисленные корни искать
зачем определять 4 таких случая, загрязняя код, если все, кроме того, что обозначено с 0, и так отсеется на первом шаге цикла. Мы ничего не выиграем по скорости, а лишь только накрутим код.
не ещё четыре, а ещё один. раз в задаче требуется округление путём отбрасывания дробной части, то при 0<Х<4 ответ будет равен 1, можно сразу его вернуть. либо если вдруг мы захотели вычислять дробную часть тоже, то в этой ветке кода можно оставить правой границей Х и дальше просто продолжить выполнять тот же алгоритм.
Обработка частных и граничных случаев это не загрязнение, а очистка кода. Объем и чистота не синонимы.
Умножение может и будет работать быстрее, я так понимаю вы предлагаете (mid*mid>x)? Там при больших числах mid (тест кейс с leetcode x=2147395599) будет переполнение и в бесконечный цикл уйдет, так как проверка будет работать неправильно. А если заморачиваться с BigInt, то может ну его нафик, пусть с делением работает
Mid*mid ни при каких условиях не будет больше максимального значения X. Я же не просто так написал, что начальную правую границу нужно сделать равной Х/2.
Чето я наврал тут. Не читайте. Можно использовать uint.
Там не надо BigInt, достаточно long long.
Мы про джаву же. Что за long long? Ну ок, пусть будет джавовский Long. Но, во-первых по условию задачи (если смотреть инициализированный код на leetcode) вход и выход имеют тип int. Ок значит внутри алгоритма мы туда сюда преобразовываем из int в long и назад когда возвращаем результат. Во-вторых long-овая математика работает дольше int-овой. По сути мы ничего не выигрываем. Конкретно в данном случае.
Ок значит внутри алгоритма мы туда сюда преобразовываем из int в long и назад
Целых 2 перобразования. На самом деле они вообще бесплатные для процессора. Ему без разницы, загрузить 64 бита в регистр EAX или 32 бита в AX.
long-овая математика работает дольше int-овой.
Не правда. Уже очень давно процессоры 64-битные. Там операции с Long и Int занимают одинаковое время.
Единственный минус Long - это работа с памятью. Если у вас большой массив данных, то работа с Int будет быстрее из-за более плотного расположения в памяти и более частого попадания в кеш при чтении. Но наша задача этим не страдает.
По сути мы ничего не выигрываем. Конкретно в данном случае.
Выигрываем то, что умножение действительно быстрее деления. Довольно сильно.
Не буду спорить. Скорее всего вы правы. Либо они одинаковы по скорости, либо очень не существенно. Я больше ориентировался не на битность процессора, а на его кеш. В голове очень давно , еще при изучении многопоточности, отложилось что в операциях с long на уровне процессора происходят оптимизации и в несинхронизированном коде (точнее без volatile) вполне реальна ситуация когда в одном потоке long переменная обновилась, а в другом потоке первые 32бита прочитались верно, а вторые закешировались и мы имеем вполне легальное, но неверное значение. Вот поэтому у меня такая мысль про long и закрепилась, что математика тут сложнее, чем с int
Это неатомарное чтение. Оно невозможно в Яве. Даже для long-ов на 64битном компьютере.
Источником неатомарный чтений является не совсем кеш, а скорее отсутствие (атомарных) машинных инструкций на чтение/запись достаточной ширины. Но для Явы это неважно, потому что спека требует атомарности всех чтений (примитивов).
если искать в пределах отрезка [0 ... 46340], то без переполнений уместится в int32
По условию задачи заданное число может быть в пределах отрезка от 0 до 2 в 31 степени - 1, поэтому mid выйдет за пределы при использовании умножения.
Но корень-то не может быть больше 46340.
ну, можете прогнать кейс с х = 2^31-1:), mid*mid вылетит за пределы int:)
а вы не забыли сделать int right = min(x, 46340); ?
А как вы определили 46340 на этапе, когда мы записываем значение right, без использования встроенных функций?
Посчитал на калькуляторе) Условие гарантирует, что прилетит число от 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))) на всё про всё, если я нигде не ошибся. Тогда можно не заморачиваться на переполнения и ничего не хардкодить.
Есть же специальная операция int32 × int32 = int64. Как раз для защиты от переполнений
Важно указать, что в условии просят решить задачу без использования встроенных функций извлечения корня или возведения в степень.
Теперь вот вопрос: у вас в статье написано, что бинарный поиск работает на упорядоченном массиве. Но в задаче у вас никакого массива вообще нет. Как так?
Ну и маленькое замечание else if (mid <= x / mid) - тут условие не нужно, ведь это ветка elsе в проверке обратного условия. Оно тут всегда выполняется.
Массива тут как таковой неочевиден, но фактически он есть. Ведь числа, которыми мы огибаем границы, как раз выстраиваются в упорядоченный массив (от 1 до Х)
С остальными замечаниями согласна, поправила/добавила:)
Массива тут как таковой неочевиден, но фактически он есть.
Я к тому, что этот момент стоит расписать поподробнее. Что на самом деле у вас есть мнимый массив, где по индексу i стоит число i^2. Ясно, что если найти в этом массиве самое большое число, не превосходящее x, то его индекс и будет ответом на задачу. Для большей ясности стоило бы задачу еще и формализовать (вроде: 
) Тогда понятно, что мы ищем в массиве.
Вместо хранения массива его значения можно просто вычислять, когда они нужны, m*m в коде - это фактически array[m]. Кстати, хорошо бы описать, почему вы вместо m*m > x используете m > x/m - это же чтобы избежать переполнения, да?
И вообще, в статье много объяснения "что", и почти нет объяснения "почему". Поэтому для людей не имеющих опыт применения дихотомии для решения подобных задач уже, ваша статья мало полезна, ибо это какая-то черная магия получается. Вот так вот двигаем границы, а почему, откуда, где тут вообще квадратный корень - этого из вашей статьи не понять.
Еще тонкий момент, а почему x=0 у вас крайний случай? Почему нельзя просто сделать l=0?
Идея понятна, но пример выбран неудачно. Быстрое вычисление квадратного корня – это очень хорошо исследованная задача, и её можно решить гораздо быстрее бинарного поиска.
Например, вот тут люди обсуждают эту тему.
Можно вычислять серединным поиском значение любой непрерывной мотонной функции (логарифма, экпоненты и т.д.). Казалось бы, решение подобных простейших задач не заслуживает размазывания на целую статью. Стыдно, но такой уж нынче Хабр победивших продактов, эйчаров и прочих чертей, не знакомых со школьными истинами.
Насчёт задач на бинарный поиск(определить их достаточно легко: 1. Отсортированный input, 2. Нас явно просят логарифмическую сложность, 3. В случае с литкодом если размер inputa > 10^6) есть один классный хак, который позволяет легко решать такие любые задачи.
Решаем/смотрим и разбираем проблему с нахождением первого true в отсортированном массиве Boolean, например [false, false, false , true, true] результат равен 3.
Запоминаем этот подход и дальше используем его как фреймворк, все, что остаётся сделать, это придумать такую функцию, которая будет для входных данных возвращать false, либо true, при этом эта функция будет монотонной (сначала только false,потом только true).
По-моему все задачи, которые я встречал на бинарный поиск, решались при помощи такого подхода
Более правильное определение бинарного поиска, особенно в вашей задаче, было бы таким - бинарный поиск, это поисковой алгоритм, который позволяет находить искомую точку на монотонной функции f(x). Зато не нужно рассказывать, что здесь есть какой-то неявный массив.
Задача предполагается для новичков, зачем усложнять код делением вместо умножения, если здесь спокойно можно использовать int64, и код становится сильно проще? Да, можно сказать, что мы экономим память, но во первых, много ли вы экономите? Во вторых, вы при этом жертвуете скоростью (деление дольше умножения), и читаемостью (умножение проще воспринимать, потому что там нет отбрасывания остатка, которое есть при делении).
Если правильно написать бин поиск, то костыль в виде переменной result, которую вы используете, станет не нужен, я не буду писать много букав, просто прикреплю код, в котором ее нет, и в котором используется более читаемый вариант с умножением. Это С++, но особо разницы я думаю нет, просто здесь long long - это int64, остальное, я думаю, все как в Java
class Solution {
public:
int mySqrt(int x) {
long long l = 0, r = x;
while (l < r) {
long long mid = (l + r + 1) / 2;
if (mid * mid > x) {
r = mid - 1;
} else {
l = mid;
}
}
return r;
}
};P. S.: про пункт 2 - если бы авторы хотели сделать задачу сложнее, они бы вместо int во входных данных, поставили int64, и вот тогда, нужно было бы напрягаться с делением, вместо умножения
Использование алгоритма бинарного поиска для нахождения квадратного корня числа на Java