Putem imbunatati solutia curenta prin folosirea catorva intrebari pentru a scurta lantul pe care ne deplasam. Astfel putem folosi n intrebari sa aflam valorile din n celule aleatoare. Apoi pornim din celula cu inaltimea cea mai joasa. In cazul in care relieful e un lant de lungime n^2 aceasta idee ne aduce la o distanta medie de n pozitii de capatul lantului, deci vom face cam 4n pasi.

Putem incerca sa eliminam jumatate din problema. Pentru asta intrebam toate valorile de pe linia din mijloc a matricei. Ne uitam la elementul minim de pe linie si la cele doua elemente vecine pe verticala cu el. Daca elementul e minim local ne oprim, daca are un vecin mai mic putem elimina jumatatea opusa vecinului. Un pas ne ia n + 2 intrebari. Ca sa rezolvam problema complet trebuie sa injumatatim solutia de log n ori deci numarul total de intrebari va fi n log n + 2 log n. Putem insa la fiecare pas sa alternam injumatatirea dupa linie cu cea dupa coloana si astfel pentru a trece de la o problema de dimensiune nxn la una de n/2 x n/2 vom face n + 2 + n/2 + 2 pasi. In total aceasta solutie va folosi 3/2 (n + n/2 + ...) + 4 log n = 3n + 4 log n pasi.

In rezolvarea unei probleme 2d ne ajuta frecvent sa rezolvam varianta ei mai simpla unidimensionala. In cazul problemei curente pentru cazul unidimensional exista o rezolvare simpla si eficienta bazata pe o idee similara cu cautarea binara.

Solutia asta are o mica scapare de care va spuneam la inceput. Incercati sa vedeti daca o gasiti inainte sa cititi mai departe.

Astfel incercam sa facem acelasi lucru in cazul bidimensional si incercam sa eliminam jumatate din problema. Pentru asta intrebam toate valorile de pe linia din mijloc a matricei. Ne uitam la elementul minim de pe linie si la cele doua elemente vecine pe verticala cu el. Daca elementul e minim local ne oprim, daca are un vecin mai mic putem elimina jumatatea opusa vecinului. Un pas ne ia n + 2 intrebari. Ca sa rezolvam problema complet trebuie sa injumatatim solutia de log n ori deci numarul total de intrebari va fi n log n + 2 log n. Putem insa la fiecare pas sa alternam injumatatirea dupa linie cu cea dupa coloana si astfel pentru a trece de la o problema de dimensiune nxn la una de n/2 x n/2 vom face n + 2 + n/2 + 2 pasi. In total aceasta solutie va folosi 3/2 (n + n/2 + ...) + 4 log n = 3n + 4 log n pasi.
 
Solutia asta are o mica scapare de care va spuneam la inceput. Incercati sa vedeti daca o gasiti inainte sa cititi mai departe. Daca ne uitam doar la minimul de pe coloana si minimul de pe linie e mai mic atunci s-ar putea sa alegem jumatatea gresita. Ce vrem e ca la fiecare pas toate elementele de pe margine a patratului in care continuam sa fie mai mari decat un element din interiorul lui. Daca ne uitam doar la coloana exista cazuri in care nu respectam aceasta proprietate.