How to find whether a number is present in the sorted matrix or not?

Question

An nxn matrix of integers both row's and column's elements are sorted in non-decreasing order. What is the best method to verify that a number is present in the array? For example if the given matrix is of 5x5.

 1  2  3  4  5
 6  7  8  9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

I searched for it but couldn't find it so I thought to ask. By the way thanks the question is having 17 answers. — , Dec 31 '14 at 20:30

score 0 · Answer 1 · answered Dec 31 '14 at 20:22

First find the row that the number must be in by performing a binary search on Column 1. If you do not find an exact match, find the number that is nearest to but less than the desired number. The desired number must be in that row.

Then, perform a binary search on that row. Either you find the number, or you do not.

score 0 · Answer 2 · answered Dec 31 '14 at 20:37

A brute force O(n^2) should not be a problem at all.

A O(log(row_count * col_count) solution would be,

public bool func_name(int[][] input, int target) {

    int row_num = input.length;
    int col_num = input[0].length;

    int b = 0, e = row_num * col_num - 1;

    while(b <= e){
        int m = (b + e) / 2;
        int mid_value = input[m/col_num][m%col_num];

        if( mid_value == target){
            return true;

        }else if(mid_value < target){

            b = m+1;
        }else{
            e = m-1;
        }
    }

    return false;
}

You could use a O(row_count+col_count) solution for which the steps would be.

intitalize row = 0 and coloumn as col_count-1

1.if input[row][coloumn]<target, increment row value.
2.If the value is greater decrement the coloumn value.

How to find whether a number is present in the sorted matrix or not?

2 Answers2