#69 Sqrt(x)

    int mySqrt(int x) {
        if (x < 2) return x;

        int left = 1;
        int right = x;
        int answer = 0;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            long long square = 1LL * mid * mid;

            if (square == x) {
                return mid;  // нашли точный корень
            } else if (square < x) {
                answer = mid;    // запоминаем mid как возможный ответ
                left = mid + 1;  // ищем большее число
            } else {
                right = mid - 1; // square > x, ищем меньшее
            }
        }

        return answer;  // возвращаем последнее подходящее значение
    }