2d array search

#1

https://ide.codingblocks.com/s/168518 i am doing it as first i am comparing in 1st column if it x is lesser then moving in the next row if x is larger then it means the element have to be present in the upper row if it exist in the matrix then i have applied binary search in that row.
only one test case is passed. also, is this a good approach in terms of complexity

#2

Hello @Learning_bunny,

As the 2D array is sorted in increasing order along each row and column,
so you should start from the top-right element.
Then do:

  1. If x is smaller than move towards left.
  2. else move one cell down.

In your approach, you are starting comparisons from the top-left element.
How would you switch between columns?
Is there any logic for that?

#3

in my code i am comparing the left most element from every row if x is larger then move to next row and else it it goes to the previous rows and apply binary search, i have updated the code with comments please check it and let me know, coz the only difference between what you said and i did is you are comparing the right most and i am doing with left most element and i am coming back to previous row if element is smaller

#4

Hello @Learning_bunny,

There are two mistakes in your code:

  1. Your code will work correct only for square matrix.
    Reason:
    Silly mistake.
    The outer loop should iterate m times and inner for n times.
    Solution:
    // for(int i=0;i<n;i++){
    for(int i=0;i<m;i++){
    // for(int j=0;j<m;j++){
    for(int j=0;j<n;j++){
    …
    }
    }

  2. As you have said that you are moving back to the previous row.
    How would you handle the test case:
    4 4
    2 4 7 9
    10 12 13 15
    17 18 20 22
    23 25 26 28
    6
    Your code will suffer TLE.

Correct it.
Hope, this would help.
Give a like if you are satisfied.

#5

for the second point can we do one that we compare a[0][0] with x before entering in to the loop and if x is smaller then exit else go inside the loop and the loop will starts from second row

#6

Hello @Learning_bunny,

Yes, you can use a conditional check that else if(x<a[j][i] && j>0) instead of using else

Hope, this is clear now.