69. Sqrt(x).txt

//Оптимальный код. Используем бинарный поиск.
//Есть правая и левая граница зоны поиска корня числа x. Правая граница = x, левая = 1. Делим зону поиска пополам, и получаем число, находящееся в самой середине этой зоны (m).
//Если перемножение этого числа на само себя (m * m) равняется исходному числу x, то значит мы нашли корень числа x, возвращаем его. Если результат перемножения больше 
//	исходного числа x, то перемещаем правую границу на число m - 1, тем самым сокращая зону поиска корня в 2 раза. Если же результат перемножения меньше исходного числа x,
//	то перемещаем левую границу на число m + 1, тоже сокращая зону поиска в 2 раза. Продолжаем цикл, пока левая и правая граница не пересекутся. В результате если мы не 
//	найдём точное решение (m * m == x) во время работы цикла, тогда возвращаем правую границу, поскольку в этом случае она будет являться наименьшим близжайшим целым
//	числом к корню числа x.
//m = l + (r - l). (r - l) для избежаения переполнения.

int mySqrt(int x) {
    if (x == 0)return x;//Если x = 0 возвращаем x
    long long l = 1, r = x;//Левая граница = 1, правая = x
    while (l <= r) {//Пока две границы не пересекутся
        long long m = l + (r - l) / 2;//Делим отрезок поиска пополам. (r - l) для того чтобы небыло переполнения.
        if (m * m == x)return m;//Если мы нашли корень числа x, то возвращаем его
        if (m * m > x)r = m - 1;//Если m^2 больше исходного x, то правая граница r = m - 1. (Уменьшаем зону поиска корня).
        else l = m + 1;//Если m^2 меньше исходного x, то левая граница l = m + 1. (Уменьшаем зону поиска корня).
    }
    return r; //Возвращаем правую границу, поскольку она является наименьшим близжайшим целым числом к корню числа x.
}


//Мой код. Добавляю новую переменную y = x, и делю её на 2, до тех пор пока y * y будет меньше исходного x. Может произойти такой случай, что мы слишком далеко уйдём от вниз
//	от верного ответа. Например sqrt(6): Делим 6 на 2 получаем 3. 3*3 > 6, повторяем цикл ещё раз. 3 / 2 = 1. Но верный ответ sqrt(6) = 2,449 т.е. 2. Поэтому прибавляем
//	к нашей переменной y единицу пока (y + 1) * (y + 1) не будет больше исходного x. 
class Solution {
public:
    int mySqrt(int x) {
        long y = x;
        while (y * y > x)
	        y = y / 2;
        while ((y + 1) * (y + 1) <= x)
	        y++;
        return y;
    }
};