Binary Search Help
- by aloh
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.
