Rădăcina pătrată întreagă prin căutare binară
Până acum ai căutat binar într-o listă. Dar căutarea binară merge pe orice șir de valori ordonate, chiar dacă nu există fizic în memorie: de exemplu toate numerele de la 0 la n. Azi calculezi partea întreagă a rădăcinii pătrate fără math.sqrt, cu doar ~31 de pași pentru numere de ordinul miliardelor.
Problema
Pentru un număr întreg n >= 0, găsește cel mai mare întreg k cu k * k <= n. De exemplu, radical(8) = 2 (pentru că 2 · 2 = 4 ≤ 8, dar 3 · 3 = 9 > 8) și radical(16) = 4.
Scrie funcția radical(n) care returnează cel mai mare întreg k cu k * k <= n, folosind căutarea binară pe intervalul [0, n]. Nu folosi math.sqrt, isqrt sau ** 0.5.
- Pornește cu st, dr = 0, n și raspuns = 0.
- Când mij * mij <= n, reține mij și caută la dreapta; altfel, caută la stânga.
- Trebuie să apară: 0, 2, 4, 1, 46339.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan