Binary Search Help

Question

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 (MID), 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. The only problem I see is that if all the matches were my target, I would basically be searching the whole array but then again, if that were the case I still would need to get all the duplicates.

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.

Answer 1

Why do you want to get away from what makes Binary search so great as soon as you find a match? Why not use a binary search on the upper half and narrow it down until you don't get any more G's, then do the same with the lower. That way in the worst case you're not searching the whole array. You find the min and max index in this way, then store those plus all of the intermediate ones in an array.

Answer 2

Check out this past question. The accepted answer uses the STL, but some of the other answers have some info that might help you.

Answer 3

Ref to the source code of lower_bound function in stl.

If you have a copy of Programming Pearls at hand or in the school library, refer to the 4th chapter and its solutions at the end of the book.

Answer 4

Notice that you're not searching for an element X, but you're searching for a boundary Y,X where Y < X and symmetrically for X,Z where X < Z. These boundaries may also be found with binary search in an imaginary array consisting of inter-element boundaries.

Answer 5

test post test post test post trying to log back in to accept answer

Answer 6

I answered this question with a solution that uses a modified binary search algorithm for arrays. As this is homework, don't click the link unless you want it spoiled, but the gist is that by tinkering with the conditions in a binary search loop, you can get it to do any of the following 3 behaviors:

1. return a match the moment it finds one (normal behavior, match can be anywhere in a run of identical values)
2. return the left-most match
3. return the right-most match

Then your question is answered by running this binary search twice, once to find the left-most match and then again to find the right-most match (only if the first run succeeded). The difference between the two results, i.e. match indices, is 1 less than the number of total matches found.