# Thread: 2D Arrays

1. Member
Join Date
Jan 2011
Posts
57
Rep Power
0

## 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. ## 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. Member
Join Date
Jan 2011
Posts
57
Rep Power
0

## Re: 2D Arrays

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

4. ## 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. Member
Join Date
Jan 2011
Posts
57
Rep Power
0

## 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. ## 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.

#### Posting Permissions

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