``````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?

3
Contributors
5
Replies
6
Views
7 Years
Discussion Span
Last Post by WaltP

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?

Edited by sonygamer: n/a

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``````

Edited by Ancient Dragon: n/a

``````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?

``````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.

``````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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.