Algoritam traženja vrha
<s>Vrh je element niza koji zadovoljava svojstvo da je veći ili jednak od svoja dva susedna elementa.</s><s>Ako imamo niz brojeva, koji su smešteni u jednodimenzionalni niz (1D) i želimo da nađemo jedan od elemenata koji je vrh, a koji ne mora da bude najveći vrh, onda ćemo koristiti algoritme traženja (pronalaženja) vrha.</s><s>Postoji nekoliko različitih načina, a to su: pronalaženje vrha u 1D nizu "Brute-Force" pretragom, i metodom "Divide and Conquer".</s><s>Takođe možemo pronaći vrh u 2D nizu (matrici) koristeći se nekim tehnikama koje primenjujemo i za 1D niz.</s>

<s>Pronalaženje vrha u 1D nizu "Brute-Force" pretragom</s>

<s>Krenućemo od početka niza i proveravati da li trenutni element ispunjava uslov vrha tj. da li su oba njegova suseda manja ili jednaka njemu.</s><s>U najgorem slučaju moraćemo da prođemo kroz ceo niz, tako da bi složenost algoritma bila linearna O(n).</s><s>Ovo je vrlo jednostavno rešenje, no nije i najbrže.</s>

<s>for i in range(n)
    if(A[i-1] <= A[i] >= A[i+1])
       return i;</s>

<s>Nalaženje vrha u 1D nizu metodom "Divide and Conquer"</s>

<s>Rešenje u logaritamskom vremenu O(logn), sa bazom 2, je dosta brže i bolje.</s><s>Koristimo metodu "podeli pa vladaj" ("Divide and conquer"), kao što se koristi u binarnom stablu pretrage.</s><s>Binarno stablo pretrage deli niz na polovine sve dok ne pronađe traženi element niza.</s><s>Sličan pristup se primenjuje u pronalaženju vrha.</s><s>Ako uzmemo niz {1, 3, 4, 3, 5, 1, 3} znamo da ako počnemo u sredini to će biti element 3, koji je manji od 4 i 5. Šta sad?</s><s>Na koju stranu treba da idemo?</s><s>Možemo ići na levu stranu i podeliti niz na pola, pa dobijamo niz {1, 3, 4} i ponovo biramo srednji element 3, ali 3 je samo veći od 1 a manji od 4, pa zato idemo na desnu stranu, ovog puta imamo samo {4} koji je ostao, pa je on naš bazni slučaj.</s><s>Dakle, imamo samo jedan element tako da je on vrh.</s>

<s>Ovo je dati algoritam gde A predstavlja niz, i početak niza i j = n-1 :</s>

<s>pronadjiVrh(A, i, j):
    m = (i + j) /2;
    if A[m-1] <= A[m] >= A[m+1]
       return m;
    else if A[m-1] > A[m] 
       return pronadjiVrh(A, i, m-1);
    else if A[m+1] > A[m]
       return pronadjiVrh(A, m+1, j);</s>

<s>Analiza složenosti algoritma</s>

<s>Prilikom rekurzije smanjujemo niz dužine n na n/2 u O(1) vremenu (tj. poređenje srednjeg elemmenta sa susedima).</s>

<s>T(n) = T(n/2) + c                   (1)
 T(n) = T(n/4) + c + c               (2)
 T(n) = T(n/8) + c + c + c           (3)
 T(n) = T(n/2k) + ck                 (4)
 smena k = log2n                     (5)
   T(n) = T(n/2log2n) + clog2n        (6)
      = T(1) + clog2n                (7)
      = O(logn)                      (8)</s>

<s>Pretraga vrha u 2D nizu "pohlepnim" algoritmom 
Pohlepni algoritam traženja 2D vrha ("Gready Ascent algorithm") bira pravac i pokušava da ga prati kako bi našao vrh.</s><s>Treba samo da se napravi model kretanja za ovaj algoritam.</s>

<s>Algoritam glasi:
 - Odabere se odakle počinje (od kog elementa) 
 - if odabrani levi (ili desni) sused veći od elementa, idemo u tom pravcu (većeg suseda)
 - else idemo u suprotnom pravcu
 - if stignemo do granice idemo dole
 - if trenutni element veci od svojih suseda, vrh je nađen</s>

<s>Za bilo koju smišljenu strategiju (tj. model kretanja), najgori slučaj složenosti će biti da se prođe kroz sve elemente matrice.</s><s>Dakle, složenost bi bila O(mn) ili ako je kvadratna matrica m = n onda O(n2).</s>

<s>Pronalaženje vrha u 2D nizu (matrica)</s>

<s>Ako nam je data matrica M dimenzija mxn, treba pronaći element matrice M[i][j] koji je veći ili jednak (>=) od svojih suseda tj. M[i + 1][j], M[i − 1][j], M[i][j + 1], i M[i][j − 1].</s><s>Postoje naravno brži i sporiji algoritmi nalaženja vrha u 2D nizu.</s>

<s>Ako je m broj kolona, a n broj redova onda algoritam glasi:
 - izaberi srednju kolonu j = m/2
 - pronađi globalni maksimum (najveću vrednost) u trenutnoj koloni
 - uporedi (i, j) sa susedima (i, j-1) i (i, j+1)
 - if (i, j-1) > (i, j) izaberi leve kolone, 
 - if (i, j+1) > (i, j) izaberi desne kolone - if (i, j) >= (i, j-1) i (i, j) >= (i, j+1) , 2D vrh (i, j) je nađen - novi problem cemo rešiti sa polovinom kolona - kada imamo jednu kolonu, naći globalni maksimum (kraj) Složenost algoritma'''
 T(n, m) = T(n, m/2) + O(n) ...
 bazni slučaj T(n, 1) = O(n) T(n, m) = O(n) + ... + O(n) ovo ce se izvršavati log2m puta konačna složenost je O(nlog2m)''
Sledi par slučajeva koje treba obraditi, kao npr. kad je niz prazan.</s>

<s>if (problem.</s><s>Length <= 0) 
    return 0; 
 if (right == -1) 
    right = problem[0].</s><s>Length; 
 int j = (left + right) / 2; 
 int globalMax = FindGlobalMax(problem, j);</s>

<s>Ovako rešavamo slučaj kada pozovemo našu metodu za vrednost right = -1.</s><s>Inicijalizujemo right sa dužinom niza, zatim izračunamo trenutnu kolonu tj. sredinu i na kraju gledamo globalni maksimum.</s><s>Pravimo pomoćnu metodu koja radi ovo.</s><s>Sve što ona radi je da ide preko istog indeksa kolone za svaki red u nizu.</s><s>Na ovaj način možemo naći indeks sa najvećim elementom u koloni.</s><s>Ovaj metod izgleda:</s>

<s>int FindGlobalMax(int[][] problem, int column) { 
    int max = 0; 
    int index = 0; 
    for (int i = 0; i < problem.</s><s>Length; i++) { 
       if (max < problem[i][column])
          max = problem[i][column]; index = i;
    }
    return index; 
 }</s>

<s>Koristimo gornje redove kolona ako ne možemo da nađemo vrednost koja je veća od trenutne.</s><s>Ako možemo onda samo povećamo indeks sve dok ne pronađemo najveći.</s><s>Sledi metoda koja proverava suseda trenutnog elementa:</s>

<s>if ( (globalMax - 1 > 0 && problem[globalMax][j] >= problem[globalMax - 1][j]) 
       && (globalMax + 1 < problem.</s><s>Length && problem[globalMax][j] >= problem[globalMax + 1][j])
       && (j - 1 > 0 && problem[globalMax][j] >= problem[globalMax][j - 1]) 
       && (j + 1 < problem[globalMax].</s><s>Length && problem[globalMax][j] >= problem[globalMax][j + 1]) 
    ) 
 { 
    return problem[globalMax][j]; 
 }</s>

<s>U ovom slučaju proveravamo četiri stvari, u svari proverićemo samo 3 stvari, jer biranjem srednje kolone koja ima samo 0, nema globalne maksimume i koristiće gornje prilikom provere suseda.</s><s>Zato i proveravamo granice, da ne bismo ništa radili izvan njih.</s><s>Nakon provere suseda, znamo da oramo da idemo levo ili desno ako je moguće, a ako nije mi smo na trenutnom globalnom maksimumu.</s><s>Ako odemo levo, postavićemo desnu granicu na trenutnu sredinu, a ako odemo desno postavićemo levu granicu na trenutnu sredinu.</s><s>Zatim ćemo raditi rekurziju ovako:</s>

<s>else if (j > 0 && problem[globalMax][j - 1] > problem[globalMax][j]) { 
    right = j; 
    return FindPeak(problem, left, right); 
 } 
 else if (j + 1 < problem[globalMax].</s><s>Length && problem[globalMax][j + 1] > problem[globalMax][j]) { 
    left = j; 
    return FindPeak(problem, left, right); 
 } 
 return problem[globalMax][j];</s>

<s>Evo celog koda za pronalaženje 2D vrha:</s>

<s>class Program { 
       static void Main(string[] args) { 
          int[][] problem = new[]{ 
          new [] {0, 0, 9, 0, 0, 0, 0}, 
          new [] {0, 0, 0, 0, 0, 0, 0}, 
          new [] {0, 1, 0, 0, 0, 8, 9}, 
          new [] {0, 2, 0, 0, 0, 0, 0}, 
          new [] {0, 3, 0, 0, 0, 0, 0}, 
          new [] {0, 5, 0, 0, 0, 0, 0}, 
          new [] {0, 4, 7, 0, 0, 0, 0}, 
       }; 
       int peak = new Program().</s><s>FindPeak(problem); 
       Console.</s><s>WriteLine("Found a peak with value : {0}", peak); 
    } 
     int FindPeak(int[][] problem, int left = 0, int right = -1) { 
       if (problem.</s><s>Length <= 0) return 0; 
       if (right == -1) right = problem[0].</s><s>Length; 
          int j = (left + right) / 2; 
          int globalMax = FindGlobalMax(problem, j); 
       if ( (globalMax - 1 > 0 && problem[globalMax][j] >= problem[globalMax - 1][j]) 
          && (globalMax + 1 < problem.</s><s>Length && problem[globalMax][j] >= problem[globalMax + 1][j]) 
          && (j - 1 > 0 && problem[globalMax][j] >= problem[globalMax][j - 1]) 
          && (j + 1 < problem[globalMax].</s><s>Length && problem[globalMax][j] >= problem[globalMax][j + 1]) ) { 
         return problem[globalMax][j]; 
       } 
       else if (j > 0 && problem[globalMax][j - 1] > problem[globalMax][j]) { 
          right = j; 
          return FindPeak(problem, left, right); 
       }  
       else if (j + 1 < problem[globalMax].</s><s>Length && problem[globalMax][j + 1] > problem[globalMax][j]) { 
          left = j; 
          return FindPeak(problem, left, right); 
       } 
       return problem[globalMax][j]; 
    } 
    int FindGlobalMax(int[][] problem, int column) { 
       int max = 0; 
       int index = 0; 
       for (int i = 0; i < problem.</s><s>Length; i++) { 
          if (max < problem[i][column]) { 
             max = problem[i][column]; index = i; 
          } 
       } 
       return index; 
    } 
 }</s>

<s>Spoljašnje veze 
 http://www.filipekberg.se/2014/02/10/understanding-peak-finding/#sthash.dgQgK8hG.dpuf
 http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf</s>

<s>Vrh</s>

