/*
 Dat je sortiran niz od N celobrojnih elemenata. Potrebno je
  prebrojati koliko se puta neki zadati broj x pojavljuje.
*/
#include <iostream>
using namespace std;

int nadjiPoslednjElementManjiOd(int x, int *niz, int levo, int desno) {
    while (levo < desno) {
        int sred = (desno == 0) ? 0 : (levo + desno) / 2 + 1;

        if (niz[sred] >= x) {
            desno = sred - 1;
        } else  {
            levo = sred;
        }
    }

    return desno;
}

int prebrojXSortiraniNiz(int *niz, int dim, int x) {
    // Specijalni slucajevi

    if (dim == 0)     return 0;
        // prazan niz

    if (x < niz[0] || x > niz[dim-1])     return 0;
        // broj ne postoji u  nizu

    // nadji kraj intervala
    int desno = nadjiPoslednjElementManjiOd(x+1, niz, 0, dim-1);

    if (niz[desno] != x)  return 0;
        // Element ne postoji
        //jer kraj intervala nije X

    // Ne mora da se prodje citav niz,
    //vec samo  levo od kraja intervala
    // Slicno, ako niz pocinje sa X, onda ce funkcija vratiti -1
    // Dakle, treba proslediti prave argumente
    // "-1" i "desno"

    int levo = nadjiPoslednjElementManjiOd(x, niz, -1, desno) + 1;

    // resenje
    return desno - levo + 1;
}





int main()
{  int a[9]={1,2,3,4,8,8,8,8,8};
   cout << prebrojXSortiraniNiz(a,9,8) << endl;
    return 0;
}