Целочисленный диапазон в квадратном корне алгоритм взлома книги кодов

Question

В java есть алгоритм для извлечения квадратного корня из квадратного корня, как показано ниже:

int sqrt(int n) {
  return sqrt_helper(n, 1, n);
}

int sqrt_helper(int n, int min, int max) {
  if (max < min) return -1; 
  int guess = (min + max) / 2·,
  if (guess *guess == n) { 
    return guess;
  } else if (guess * guess < n) { 
    return sqrt_helper(n, guess + 1, max); 
  } else {  
    return sqrt_helper(n, min, guess - l); 
  }
}

Вопрос:

Поскольку min и max являются целыми числами,они могут иметь любые значения в диапазоне, например max = Integer.MAX_VALUE

Так что не беспокойтесь о guess = (min + max) / 2, так как он пересечет допустимый диапазон, или guess *guess также.

Answer 1

Поскольку вы упоминаете «Взлом интервью по кодированию» ...

Обычно в контексте среднего интервью по кодированию не стоит беспокоиться о деталях, связанных с реализацией, таких как эта.Интервьюер пытается подтвердить базовую компетентность и понимание - им редко захочется запускать ваш код, и вам обоим должно быть дано понять, что алгоритм сломается в экстремальных пределах базовых типов данных вашего языка.Если интервьюер спрашивает конкретно об ограничениях, то вы могли бы кратко упомянуть, что функция потерпит неудачу для значений, превышающих (Integer.MAX_VALUE / 2) в этом языке.

Ограничение будет применяться практически к любому алгоритму, для которого вы пишетесобеседование по кодированию, и ни один разумный интервьюер не ожидает, что вы специально разработаете свое решение для смягчения такого рода крайнего случая.Я был бы очень обескураживающим, если бы я попросил кандидата написать функцию, которая производит числа Фибоначчи, и они потратили время, пытаясь оптимизировать случай, когда выходные данные превышают 16-значные значения.

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

Answer 2

Существуют простые способы решения этой проблемы (например, min + (max - min) / 2).

Более серьезная проблема переполнения целых чисел - guess * guess.Вы можете изменить тест для сравнения guess с n / guess, который медленнее, но обычно не переполняется.Или вы можете использовать небольшой взлом, чтобы найти лучшую отправную точку (clz здесь полезно, если у вас есть), поскольку вы должны быть в состоянии найти предположение, квадрат которого находится в диапазоне представимых целых чисел.

Интервьюер мог бы быть еще более впечатлен, если бы вы смогли предоставить алгоритм Ньютона-Рафсона , который сходится очень быстро.

Answer 3

Вы должны подтвердить свой язык.Но в псевдокоде вы можете сделать что-то вроде:

int guess = ((min.ToBigInt() + max.ToBigInt()) / 2).ToInt()