Problem
Die ganzzahlige Quadratwurzel von n ist die abgerundete Quadratwurzel, also die größte ganze Zahl r mit r × r ≤ n. Die Wurzelfunktionen der Standardbibliothek rechnen mit Gleitkommazahlen und können bei großen Eingaben um eins danebenliegen. Rechne deshalb nur mit ganzen Zahlen, zum Beispiel mit einer binären Suche über die möglichen Ergebnisse.
Implementiere integer_square_root(n).
Eingabe
n: Eine nicht negative ganze Zahl.
Ausgabe
Gib die größte ganze Zahl r zurück, für die r × r ≤ n gilt.
Einschränkungen
0 ≤ n ≤ 10^18
Beispiele
Eingabe:
n = 50
Erwartete Ausgabe:
expected = 7
Eingabe:
long long n = 50;
Erwartete Ausgabe:
long long expected = 7;
Eingabe:
long n = 50;
Erwartete Ausgabe:
long expected = 7;
Erläuterung
7 × 7 = 49 ≤ 50, aber 8 × 8 = 64 > 50, also lautet die Antwort 7.
Eingabe:
n = 144
Erwartete Ausgabe:
expected = 12
Eingabe:
long long n = 144;
Erwartete Ausgabe:
long long expected = 12;
Eingabe:
long n = 144;
Erwartete Ausgabe:
long expected = 12;
Erläuterung
144 ist genau 12 × 12, also lautet die Antwort 12.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Das Ergebnis liegt zwischen 0 und n, und r × r wächst mit r. Du kannst den Bereich also in jedem Schritt halbieren.
Hinweis 2
Bei großem n kann r × r überlaufen. Vergleiche stattdessen r mit n / r oder begrenze die obere Schranke.
Hinweis 3
Prüfe kleine Eingaben wie 0, 1 und 3 von Hand.
Erwartete Komplexität
Zeit O(log n), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.