function count(tab, w, n)
{
//index of the first appearance
idMin = first(tab, 0, n-1, w, n);
//if 'w' doesn't exists in tab
if (idMin == -1) { return idMin };
//index of the last appearance
idMax = last(tab, idMin, n-1, w, n);
how_many = idMax-idMin+1;
//return number of occurrences
return how_many;
}
function first(tab, l, p, w, n) //index of the first appearance
{
if (l <= p) //l - beginning index of the searching list, p - last index od the searching list
{
mid = Math.floor((l+p)/2); //middle index
if ((mid == 0 || w > tab[mid-1])&&(tab[mid] == w)) //mid == 0 when tab has one element
{
return mid;
}
else if(w > tab[mid])
{
return first(tab, (mid+1), p, w, n);
}
else
{
return first(tab, l, (mid-1), w, n);
}
}
return -1;
}
function last(tab, l, p, w, n)//index of the last appearance
{
if (l <= p)
{
mid2 = Math.floor((l+p)/2);
if ((mid2 == n-1 || w < tab[mid2+1]) && (tab[mid2] == w))
{
return mid2;
}
else if (w < tab[mid2])
{
return last(tab, l, (mid2-1), w, n);
}
else
{
return last(tab, (mid2+1), p, w, n);
}
}
//return -1; it is necessary?
}
var tab = [1, 2, 3, 3, 4, 5, 6, 7, 7, 7, 8, 9]
, w = 7 // looking value
, n = tab.length // length of the tab
;
counts = count(tab, w, n);
document.write("Number " + w + " occurred " +counts+ " times<br/>");
question from:
https://stackoverflow.com/questions/65939215/time-complexity-of-the-algorithm-javascript