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.

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.

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. Putem face asta pentru ca exista un lant descrescator ce trece prin elementul minim al liniei si vecinul lui vertical mai mic care intra in jumatatea corespunzatoare vecinului si nu mai poate iesi din ea. 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. Solutia poate fi reparata usor: la fiecare pas alegem jumatatea in care se afla minimul elementelor cercetate pana acum.

*Problema inrudita:*
Daca avem un arbore binar cu n noduri. Fiecare nod are o valoare in el. Care e numarul minim de intrebari in care puteti garata ca gasiti un minim local.

*Probleme inrudite:*
Daca avem un arbore binar cu n noduri. Fiecare nod are o valoare in el. Care e numarul minim de intrebari in care puteti garanta ca gasiti un minim local?
 
_Maxim (Lot 2005)_ Se da un sir circular A de n elemente distincte (n <= 1000000). Se cere sa determinati un maxim local in cel mult 25 de intrebari. O intrebare ask(i, j, k) ne spune ordinea lui A[i] fata de A[j] si ordinea lui A[j] fata de A[k].

Problema "Minim local" e din paperul "Local optimization on graphs" de Llewellyn, Donna Crystal, Tovey, Craig si Trick, Michael.