finding number of times a number appears in an array

[sonygamer]

int found=false;
	int first=0;
	int last= arraysize-1;
	int count2=0;
	while(first<=last && found==false)
	{
		int loc=(first+last)/2;
		if(key<sorted_array[loc])
			last=loc-1;

		else
		{
			if(key>sorted_array[loc])
				first=loc+1;
			else
				if(key==sorted_array[loc])
				{
					first=loc+1;
					count2++;
					
				}
				else
					found=true;
				
		}
		
	}
	cout<<"the number of students with this grade are: "<<count2<<endl;

I have already sorted an array of size 100 so its in ascending order. I am using this binary search to find how many times a number, which i have called KEY is found in this sorted_array[100]. so far this part:

if(key==sorted_array[loc])
				{
					first=loc+1;
					count2++;
					
				}
				else
					found=true;

does count the ammount of numbers which match the key, BUT it only counts the ones above LOC, which is the middle. Basically its ignoring any numbers that might match the KEY that lie below LOC. Is there some way to get it to count these numbers below LOC that match the key?

[sonygamer]

okay this is the new part that i replaced:

int found=false;
	int first=0;
	int last= arraysize-1;
	int count2=0;
	while(first<=last && found==false)
	{
		int loc=(first+last)/2;
		if(key<sorted_array[loc])
			last=loc-1;

		else
		{
			if(key>sorted_array[loc])
				first=loc+1;
			else
				if(key==sorted_array[loc])
				{	
					
					if(key=sorted_array[first])
					{count2++;}
					//first=first;	
					count2++;
					sorted_array[loc]=0;
					first++;
						if(sorted_array[first]=0)
						first=first+1;
					
				}
				else
					found=true;
				
		}
		
	}
	cout<<"the number of students with this grade are: "<<count2<<endl;

this time it'll either tell me exactly how many numbers in the array match the KEY, or it'll give my the number that does -1. Like if there are 3 numbers that match the KEY, sometimes it'll give me 3 as the answer or it'll give me 2 as the answer. Some times if there are 5-7 that match the KEY, it'll give me 2 as the answer. Can someone tell me how to fix this?

[Ancient Dragon]

1. Use binary search to locate an instance of the number it should be looking for.

2. Back up the list until you find the index whose value is different than the one you want. That will give you the starting counting point.

3. Search forward until it finds a different value, counting the number of instances along the way.

int key = 3;
int index, i;
int array[] = {1,2,3,3,3,3,4,4,4,5,5,5};
int size = sizeof(array)/sizeof(array[0]); // number elements in array
// This will get you the index into the array where key is found
int found = binary_search( array, size, key); 

// now back up until either the beginning of the array or the first array 
//value that is NOT key
for(i = found; i >= 0; --i)
{
    if( array[i] != key)
       break;
}

// now count the number of values in the array that
// are the same as key
int counter = 0;
while(i < size && array[i] == key)
   ++counter;

// now you should have the correct recult

[sonygamer]

int found=false;
	int first=0;
	int last= arraysize-1;
	int count2=0;
	while(first<=last && found==false)
	{
		int loc=(first+last)/2;
		if(key<sorted_array[loc])
			last=loc-1;

		else
		{
			if(key>sorted_array[loc])
				first=loc+1;
			else
				if(key==sorted_array[loc])
				{	
					for(i=loc;i>=0;i--)
					{
						if(sorted_array[i] != key)
							break;
					}
					while(i <= arraysize && sorted_array[i]==key)
						count2++;
				}
				else
					found=true;
					
				
		}
		
	}
	cout<<"the number of students with this grade are: "<<count2<<endl;

}

ok so this is what i have now. The problem is that even if I leave the bottom-most while loop inside the for-loop that preceded it or where it is right now, when i run the program it seems to be stuck in an infinite loop. How do i fix this?

[sonygamer]

int found=false;
	int first=0;
	int last= arraysize-1;
	int count2=0;
	while(first<=last && found==false)
	{
		int loc=(first+last)/2;
		if(key<sorted_array[loc])
			last=loc-1;

		else
		{
			if(key>sorted_array[loc])
				first=loc+1;
			else
				if(key==sorted_array[loc])
				{	
					for(i=loc;i>=first;i--)
					{
						if(sorted_array[i] != key)
							first=loc-1;
					}
					if(key=sorted_array[first])
					{
						count2++;
						first++;
					}
				}
				else
					found=true;
		}
		
	}
	cout<<"the number of students with this grade are: "<<count2<<endl;

alright this one actually runs without running around in an infinite loop. The only problem that exists now is that sometimes count2 still sometimes returns 1- a few numbers less than the actual amount of numbers that are equal to KEY.

[WaltP]

for(i=loc;i>=first;i--)
{
	if(sorted_array[i] != key)
		first=loc-1;
}

A while loop would be better here...

if(key=sorted_array[first])
{
	count2++;
	first++;
}

... and here.