Rădăcina pătrată întreagă prin căutare binară C++

Rădăcina pătrată întreagă a lui n este cel mai mare întreg r pentru care r²≤n. Pentru 20, răspunsul este 4, deoarece 16≤20, dar 25>20. Aceasta este o cerință exactă pe întregi, nu o rotunjire la cel mai apropiat număr.

O proprietate care nu se schimbă înapoi

Pentru n fix, condiția r²≤n este adevărată pentru valorile mici și falsă după o anumită frontieră. Se numește o proprietate monotonă: odată trecută frontiera, nu revine la adevărat. Căutarea binară exploatează această ordine, eliminând jumătate din interval la fiecare pas.

Citim 0≤n≤10^18. Căutăm în intervalul 0..10^9, deoarece (10^9)²=10^18. Păstrăm separat cel mai bun rezultat valid găsit. Dacă mijlocul m este valid, încercăm valori mai mari; altfel, continuăm la stânga.

Comparație fără produs intermediar

Pentru m>0, condiția m²≤n este echivalentă cu m≤n/m. Folosim această formă pentru a evita depășirea tipului într-o înmulțire dacă ulterior adaptăm limitele. Pentru m=0, rezultatul este întotdeauna valid; verificarea lui apare înaintea împărțirii.

Pătratele lui 3,4,5 sunt 9,16,25. Ultima valoare al cărei pătrat nu depășește 20 este 4.Mărește schema ↗

#include <iostream>
using namespace std;
int main() {
    long long n; cin >> n;
    long long st=0,dr=1000000000,raspuns=0;
    while(st<=dr) {
        long long m=st+(dr-st)/2;
        if(m==0 || m<=n/m) { raspuns=m; st=m+1; }
        else dr=m-1;
    }
    cout << raspuns << '\n';
}

Operatorul || înseamnă „sau” și nu mai evaluează a doua condiție când prima este adevărată. Astfel, pentru m=0 nu executăm n/m. Fiecare ramură elimină și mijlocul verificat, prin m+1 sau m-1; intervalul nu poate rămâne neschimbat.

Verificare prin vecinii răspunsului

Nu este suficient ca r²≤n. Trebuie să verifici și că (r+1)²>n; altfel r poate fi un răspuns prea mic. Pentru 16, răspunsul este 4. Pentru 15, este 3, iar pentru 17 rămâne 4. Aceste trei teste verifică exact frontiera pe care o căutăm.

Timpul este O(log(10^9+1)), aproximativ 30 de înjumătățiri pentru domeniul ales, și memoria O(1). Citim o singură valoare, deci nu există un cost ascuns de parcurgere a unui vector.

Exersează

Testează 0, 1, 15, 16, 17 și 10^18. Răspunsurile sunt 0, 1, 3, 4, 4 și 10^9. Ca extensie, verifică dacă n este pătrat perfect după calcularea rădăcinii întregi. Pentru limitele de aici, produsul r·r încape în long long.

Continuă cu căutarea binară, funcțiile matematice și alegerea tipurilor.

Întrebări frecvente

Ce este rădăcina pătrată întreagă a unui număr?

Este cel mai mare întreg r pentru care r²≤n. Pentru n=20, rezultatul este 4: 4²≤20, dar 5²>20. Nu este rotunjirea la cel mai apropiat întreg.

De ce pot căuta binar radicalul întreg?

Condiția r²≤n este monotonă pentru r nenegativ: este adevărată până la o frontieră și falsă după ea. Căutarea binară localizează ultima valoare care o respectă.

Cum evit overflow-ul când verific pătratul candidatului?

Pentru un candidat r pozitiv și n nenegativ, compară r <= n / r în loc să calculezi r*r. Tratează separat r=0, pentru a nu împărți la zero.