binary search

[michy]

hi experts again, =)
today i have a problem to ask about binary search.
binary algorithm:

int binarySearch(int x[], int searchItem){
while(start <= end){
	mid=(start+end)/2;
	if(searchItem == x[mid]) return(mid);
	else if(y > x[mid])	start=mid+1;
	else if(y < x[mid]) end=mid-1;		
}
return(-1);
}

the algorithm should be something like this rite?

now the problem comes, if in my array x[]={1,2,3,3,4,5}
there are two 3 in the array, so my binary function may only return 1 value. So any idea/ guideline to solve this problem?
my idea is create a new function to check it after a return value.
is there any better way to do it?
thx in advance!

[helios]

That's the way binary search works. Furthermore, the algorithm is only required to return any of the elements that are equal to the value passed, to be correct.

[kempofighter]

Well if you want to write an algorithm that finds all elements that match the input then I guess you need a different algorithm such as a counting algorithm. Is that what you want? That would be more of a linear style algorithm that simply searches the entire container and counts the number of elements. Or perhaps you want something like a lowerbound/upperbound function that allows you to make one call to get the lower bound and another to get the upper bound. Then the diff between the iterators can tell you how many occurrences exist for the value that you are searching for.