searching in 2d array as O(n) with unsorted rows

Question

I need to write a method that takes 2d array 'int [][] m' and a value 'val' and check if val is in the array in the complexity of O(n) while n defined as the number of rows and m must be squared

The array that can use as a parameter for my method must return true for this method:

(if it returns true so the array is as requested)

public static boolean test(int[][] m) {
    int n = m.length;
    for (int r = 0; r < (n - 1); r++)
        for (int c = 0; c < n; c++)
            for (int i = 0; i < n; i++)
                if (m[r][c] > m[r + 1][i]) return false;
    return true;
}

This array returns TRUE:

int [][] arr3 = new int [][]{
    { 0,   2,    1,    2,   0,  5,   5,   5,  },
    { 21,  21,   7,    7,   7,  21,  21,  21 ,},
    { 21,  21,  21,   21,  21,  21,  21 , 21, },
    { 21,  21,  23 ,  42,  41,  23,  21,  21, },
    { 60  ,56,  57,   58,  53,  52,  47,  51 ,},
    { 61,  65,  70 ,  72,  73,  78,  82,  98 ,},
    { 112, 121, 112, 134, 123, 100,  98,  111,},
    { 136, 136, 136, 134, 147, 150,  154, 134,},
};

My method should return true if val is in the array and looks like this:

public boolean findValTest(int [][] m, int val){...}

Answer 1

your solution is here. i made a function that do binary search for first column. if the val find in the first column the function return true, else last period of 'l' and 'r' are benefit for us. 'r' and 'l' are always equal of have only one distance(r=l or abs(r-l)=1 ). lower bound of 'r' and 'l' are expected row that the val maybe exist in it. so we should search this row.
O(n) for binary search is Log(n) and for row search is n. so the final O(n) will be n.code is here:

static boolean binarySearch(int arr[][], int l, int r, int x)
{
    if (r>=l)
    {
        int mid = l + (r - l)/2;

        // If the element is present at the 
        // middle itself
        if (arr[mid][0] == x)
           return true;

        // If element is smaller than mid, then 
        // it can only be present in left subarray
        if (arr[mid][0] > x)
           return binarySearch(arr, l, mid-1, x);

        // Else the element can only be present
        // in right subarray
        return binarySearch(arr, mid+1, r, x);
    }

    // We reach here when element is not present
    //  in array

    int row = Math.min(l,r);
    for(int i=0; i<arr[0].length ;i++)
      if(arr[row][i]==x)
        return true;
    return false;
}

Answer 2

It is possible iff. the matrix m is a square matrix of size n x n. Core idea is inspired by oleg.cherednik's answer. As soon as we find a row in m, such that m[row][0] >= val, we know that val must be in either row row or row - 1(since the same comparison on row - 1 was false). Thus, we have to find our candidate rows (O(n)) and then analyze only those two rows (also O(n)). If m is not square, but rectangular, the algorithm has a complexity of O(n + k), where n is the number of rows and k is the number of colums in m. This leads to the following algorithm.

public class Test {

  public static boolean contains(final int[][]m, final int value) {
    int candidateRow = m.length;
    for (int row = 1; row < m.length; ++row) {
      if (m[row][0] == value) {
        return true;
      }
      if (m[row][0] > value) {
        candidateRow = row;
        break;
      }
    }

    for (int val : m[candidateRow - 1]) {
      if (val == value) {
        return true;
      }
    }

    if (candidateRow < m.length) {
      for (int val : m[candidateRow]) {
        if (val == value) {
          return true;
        }
      }
    }
    return false;
  }

  public static void main(String[] args) {
    int [][] testArray = new int [][]{
        {   0,   2,   1,   2,   0,   5,   5,   5 },
        {  21,  21,   7,   7,   7,  21,  21,  21 },
        {  21,  21,  21,  21,  21,  21,  21,  21 },
        {  21,  21,  23,  42,  41,  23,  21,  21 },
        {  60,  56,  57,  58,  53,  52,  47,  51 },
        {  61,  65,  70,  72,  73,  78,  82,  98 },
        { 112, 121, 112, 134, 123, 100,  98, 111 },
        { 136, 136, 136, 134, 147, 150, 154, 134 }
    };
    for (int[] row : testArray) {
      for (int val : row) {
        System.out.print(contains(testArray, val) + " ");
      }
      System.out.println();

    }
    System.out.println();
    System.out.println();
    final int[] notInMatrix = { -1, 3, 4, 6, 8, 22, 30, 59, 71, 113, 135 };
    for (int val : notInMatrix) {
      System.out.print(contains(testArray, val) + " ");
    }
    System.out.println();
  }
}

We can improve the acutal runtime by determining the candidate lines through a binary search algorithm so that candidate lines are found in O(log(n)) instead of O(n). The asymptotical runtime will still be O(n) for square matrices and O(log(n) + k) for non-square n x k matrices. The idea for this was taken from Saeed Bolhasani's answer.

  private static int findCandidateRow(final int[][] m, final int value) {
    int lower = 0;
    int upper = m.length;
    int middle = (upper + 1) / 2;
    while (middle != m.length 
        && middle != 1
        && (m[middle][0] < value || m[middle - 1][0] > value)) {
      if (m[middle][0] < value) {
        lower = middle;
      } else {
        upper = middle;
      }
      middle = lower + (upper - lower + 1) / 2;
    }
    return middle;
  }

Answer 3

Smth. like that. In case of Every number at row i is equals or smaller then every number on row i+1, than you can check only first element in each row to define a row, where required value could be. Element in unsorted row can be found only with full scan.

This algorithm have to scan 2 full rows only, which is O(n) where n - number of rows.

public static boolean findValTest(int[][] m, int val) {
    for (int row = 0; row < m.length; row++) {
        if (m[row][0] <= val && row != m.length - 1)
            continue;

        int r = row;

        while (r >= row - 1 && r >= 0) {
            for (int col = 0; col < m[r].length; col++)
                if (m[r][col] == val)
                    return true;

            r--;
        }

        return false;
    }

    return false;
}

Test cases:

System.out.println(findValTest(arr3, -1)); // false
System.out.println(findValTest(arr3, 5)); // true
System.out.println(findValTest(arr3, 7)); // true
System.out.println(findValTest(arr3, 55)); // false
System.out.println(findValTest(arr3, 47)); // true
System.out.println(findValTest(arr3, 147)); // true
System.out.println(findValTest(arr3, 200)); // false
System.out.println(findValTest(new int[][] { { 3, 4, 5 } }, 4));   // true