Results 1 to 6 of 6

Thread: 2D Arrays

  1. #1
    Billywizz is offline Member
    Join Date
    Jan 2011
    Posts
    57
    Rep Power
    0

    Default 2D Arrays

    Hi could anyone give an example of how to search a sorted square 2d array with binary search (i assume that is the quickest if not i would love to hear other ideas)

    2D array is sorted in both rows and collumns eg.

    2 4 5 6 8
    3 6 7 8 10
    5 8 9 12 13
    6 10 11 13 14
    8 14 15 17 19

    Any examples would really be appreciated so i can get my head round it even pseudo code
    Thanks.

  2. #2
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default Re: 2D Arrays

    Depends upon what you are trying to achieve. What should the search yield if it searches for 8? (since there are four occurrences of that value)

  3. #3
    Billywizz is offline Member
    Join Date
    Jan 2011
    Posts
    57
    Rep Power
    0

    Default Re: 2D Arrays

    should return true as soon as it finds 8 is a match to the input value

  4. #4
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default Re: 2D Arrays

    2 4 5 6 8
    3 6 7 8 10
    5 8 9 12 13
    6 8 11 13 14
    8 14 15 17 19

    Binary search starts in the middle and halves the elements each iteration until it either finds the target or it can determine the target is not present. Using the above modified matrix the middle value would be the 9 and we are searching for 10. Since 10 is greater then we would look in the upper half but a quick glance reveals that 10 is in the lower half. What if we go by rows and are searching for 7. We look at the first element of row index 2 which is 5. Since 7 is greater we look in the upper half. Again this falis as 7 is in the lower half.

    I doubt binary search can be applied to a 2D matrix unless the values are in sequential order:
    1 2 3 4 5
    7 8 11 12 14
    15 17 18 19 22
    25 26 27 31 34

  5. #5
    Billywizz is offline Member
    Join Date
    Jan 2011
    Posts
    57
    Rep Power
    0

    Default Re: 2D Arrays

    Dont worry iv done it now you definatly can just got to use divide and conquer to eliminate the bottom right quadrant and keep doing it recursivly.

  6. #6
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default Re: 2D Arrays

    Really! I just provided 2 examples where binary search fails. Just because your code succeeds does not mean it will in all situations.

Similar Threads

  1. arrays and multidimensional arrays
    By belfast09 in forum New To Java
    Replies: 5
    Last Post: 06-14-2011, 01:28 PM
  2. store array of arrays in array of arrays
    By joost_m in forum New To Java
    Replies: 4
    Last Post: 04-19-2010, 10:32 AM
  3. Arrays.sort... why sorting all arrays in class?
    By innspiron in forum New To Java
    Replies: 6
    Last Post: 03-23-2010, 01:40 AM
  4. Arrays
    By tejens23 in forum New To Java
    Replies: 5
    Last Post: 11-25-2009, 10:46 PM
  5. Arrays
    By hypes057 in forum New To Java
    Replies: 13
    Last Post: 09-04-2009, 10:40 AM

Posting Permissions

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