-1

We have an n x n matrix, where every row and column is sorted in increasing order.

Given a number x, how to decide whether this x is in the matrix, better than O(n) complexity?

aerin
  • 20,607
  • 28
  • 102
  • 140
  • better than O(n) complexity? I don't think its possible. – xrisk Apr 06 '17 at 23:08
  • What have you tried that doesn't work? – Gene Apr 06 '17 at 23:12
  • @Gene I can do it O(n) just by simply search by rows and columns. – aerin Apr 06 '17 at 23:14
  • @Toussaint Louverture that aproach is O(N2) because for nXn matrix , rows =n and columns = n. For each row you traverse n column elements. – nits.kk Apr 07 '17 at 01:36
  • This is a famous question, you would have got it eaisly if you would have tried searching for the solution. https://youtu.be/ZhG1M_FzxgI and also http://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/ are two such places for the solutions, which are there in the search results, there are others too. – nits.kk Apr 07 '17 at 01:41
  • 1
    @nits.kk But these are O(n) solutions. He's asking for better than O(n). – Gene Apr 07 '17 at 03:42
  • It's pretty easy to construct an information theoretic adversary argument that O(n) is the best you can do. I'll let you work out the details. – Gene Apr 07 '17 at 03:44
  • @nits.kk if you start from the left bottom, then it's O(m+n), NOT O(n^2). m is the number of row, n is the number of column. Why would anyone go through all of the cells if it's sorted..-_- – aerin Apr 07 '17 at 05:16

1 Answers1

2

I think that just use binary search.

Time complexity of Binary search is O(log(n)).

So, in case n x n matrix, time complexity is O(log(n^2)) = O(2log(n)).

It is better than O(n).

-----(edit) / this is my cpp code.

#include<vector>
#include<iostream>
#include<cstdio>

using namespace std;

int n = 10;
vector<vector<int> > arr;
int search_cnt;

int _1to2(int x)
{
    int row, col;

    row = (x - 1) / n + 1;
    if(x % n == 0)
        col = n;
    else
        col = x % n;

    return arr[row][col];
}

int _2to1(int row, int col)
{
    return (row - 1) * n + col;
}

int binary(int find)
{
    int low = 1, high = n*n, mid;

    while(low <= high)
    {
        search_cnt++;
        mid = (low + high) / 2;
        if(_1to2(mid) > find)
            high = mid - 1;
        else if(_1to2(mid) < find)
            low = mid + 1;
        else
        {
            printf("search_cnt = %d, ", search_cnt);
            return mid;
        }
    }

    return -1;
}

int main()
{
    int cnt = 1;
    search_cnt = 0;

    arr.resize(n+1);
    for(int i = 0; i <= n; i++)
        arr[i].resize(n+1);

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            arr[i][j] = cnt++;

    for(int i = 1; i <= n*n; i++)
    {   
        printf("searching pos = %d \n", binary(i));
        search_cnt = 0;
    }

    return 0;
}
jingbe
  • 59
  • 6
  • 1
    Binary search works on a total order. A 2d array with sorted rows and columns is not totally ordered. How are you going to use binary search? I'd like to see pseudocode. – Gene Apr 07 '17 at 03:40
  • If matrix is ordered row to column and matrix cell start (1,1), I can think each cell (arr[y][x]) is 1d array ( arr[p], p = (x - 1) * n + y ). – jingbe Apr 07 '17 at 04:14