Thread: C++ problem with binary search algorithm

Hello,
I have to made a programme which will search for given number and it must work in O(log(n)). The problem is that this programme beside finding this number have to find how many times this given number is used in this sequence.

Sequence is from lowest to highest only one possibility to use binary search algorithm

For example when we have squence
-1 -2 3 3 3 3 4 5 6 7 7 8 9 9 9 9 10
The numbers we need to search are
1 , 3 , 7 , 9 , 11 , 12
The answer is
0 , 4 , 2 , 4 , 0 , 0
So we need to find the sum of used number in sequence.

I have written algorithm

Code:

int start = 0; 
int end = sequencelenght - 1; 
int mid = 0;  
/// Binary serach
while (start<=end) {
   int mid=(start+end)/2; 
   if (sequence[mid]==givennumber) {
   intright=mid+1; 
   int left=mid-1;
   sum++; 
/// Here is problem with searching duplicates its O(n) not O(log(n))
   while(left >= pocz && array[left]==givennumber){
                            sum++;
                            left--;
                        }
  while(right <= end && array[right]==givennumber){
                            sum++;
                            right++;
                        }
////// End of problem ///////
 cout << sum;
                        break;
                    } 
  if (array[mid]<givennumber) {
     start=mid+1;
  } else {
     end=mid-1;
                    }
                }
    if(sum==0)
                {
                    cout << "0";
}
}

As u see i search for given numer with binary with O(log(n)) but when i have to sum the duplicates the only good way i see is using loop to right and left but this have got log(n) specification
(becouse when sequence would be for example
7 7 7 7 7 7 7 7 7 and given number to search will be 7 this will be O(n) loop).
Can somebody tell me how would look the most optimal algorithm look for this exercise? I mean O(log(n)) the fastest algorithm becouse i have no idea how to do this better.

Sorry for my English and thanks for help.

Only one idea what comes to my is to doing binary search to find duplicats i mean when we find given number in search we know about 2 positions left and right we can delete this and again do search binary for given number and repeat this and repeat but i dont know that if this will be O(log(n)) or O(2log(n)) and i still dont know that would be most optimal algorithm or not. (repeating binary search)

Yep but i cannot make id recursively i must do it with using iteration (I dont know how to write it correctly)