
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.

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)

Re: 2D Arrays
should return true as soon as it finds 8 is a match to the input value

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

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.

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.