# Binary Search Help

• 03-13-2010, 06:06 AM
Plissken
Binary Search Help
Hi, for a project I need to implement a binary search. This binary search allows duplicates. I have to get all the index values that match my target. I've thought about doing it this way if a duplicate is found to be in the middle:

Target = G
Say there is this following sorted array:

B, D, E, F, G, G, G, G, G, G, Q, R S, S, Z

I get the mid which is 7. Since there are target matches on both sides, and I need all the target matches, I thought a good way to get all would be to check mid + 1 if it is the same value. If it is, keep moving mid to the right until it isn't. So, it would turn out like this:

B, D, E, F, G, G, G, G, G, G, Q, R S, S, Z

Then I would count from 0 to mid to count up the target matches and store their indexes into an array and return it.

That was how I was thinking of doing it if the mid was a match and the duplicate happened to be in the mid the first time and on both sides of the array.

--------
Now, what if it isn't a match the first time? For example:

B, D, E, F, G, G, J, K, L, O, Q, R, S, S, Z

Then as normal, it would grab the mid, then call binary search from first to mid-1.

B, D, E, F, G, G, J

Since G is greater than F, call binary search from mid+1 to last.

G, G, J.

The mid is a match. Since it is a match, search from mid+1 to last through a for loop and count up the number of matches and store the match indexes into an array and return.

Is this a good way for the binary search to grab all duplicates? Please let me know if you see problems in my algorithm and hints/suggestions if any.

Thank you

BTW, my instructor said we cannot use Vectors, Hash or anything else. He wants us to stay on the array level and get used to using them and manipulating them.
• 03-13-2010, 06:38 AM
gcalvin
Consider the case where you have 100 values and they ALL match your search target. You hit #50 right away, and then go looking one at a time in each direction. You'll end up looking at all 100 values. If you keep doing binary search to look for the endpoint (either the beginning and end of the array, or a value on each side that doesn't match, and then keep using binary search to track down the boundary), you'll end up looking at about 15 values max. And that's just with 100 values -- imagine if it's 1,000,000.

On the other hand, if there's just one matching value out of 100, and it's right at the midpoint, you'll still end up looking at about 15 values, instead of just 3. Still, I think the tradeoffs favor using binary search all the way.

-Gary-
• 03-13-2010, 11:34 AM
Plissken
Thanks. I've figured out a solution.