Results 1 to 3 of 3
  1. #1
    Plissken is offline Member
    Join Date
    Feb 2010
    Posts
    4
    Rep Power
    0

    Default 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.
    Last edited by Plissken; 03-13-2010 at 06:11 AM. Reason: extra information

  2. #2
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    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-

  3. #3
    Plissken is offline Member
    Join Date
    Feb 2010
    Posts
    4
    Rep Power
    0

Similar Threads

  1. Binary search tree search method
    By chopo1980 in forum New To Java
    Replies: 2
    Last Post: 12-10-2009, 02:42 AM
  2. Binary Search Tree
    By michael_mke in forum New To Java
    Replies: 3
    Last Post: 12-04-2008, 03:03 AM
  3. Recursive Binary Search
    By EternalSolitude in forum New To Java
    Replies: 2
    Last Post: 11-21-2008, 07:26 AM
  4. Binary Search in Java
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-15-2008, 08:43 PM
  5. binary search
    By tranceluv in forum New To Java
    Replies: 10
    Last Post: 01-14-2008, 08:13 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •