値がO（n）時間の2D配列に含まれているかどうかを調べる方法は何ですか？

Question

私は2次元配列（すべての行の要素が左から右に向かって増加するように配列され、各列の要素は上から下に向かって増加するように配列されています）とintを返し、intが2D配列内にあるかどうかを調べます。ネストされたループを使いたいのですが、それはO（N^2）時間になるでしょう。したがって、intがサブ配列の1つで最初のものよりも小さく、最後のものよりも大きければテストし、そうであれば次のサブ配列に移動する条件を作成しようとしています。ここに私が持っているものがあります：

static boolean has(int number, int[][] a) { 
    int q = 0; 
    boolean c = false; 

    for (int i = 0; i < a[q].length-1; i++){ 
     if ((number < a[i][q]) || (number > a[a[j].length-1][i])){ 
     q++; 
     } 
     else if (number == a[i][q]){ 
     c = true; 
     break; 
     } 
     else c = false; 
    } 
    return c; 
    } 

は、いくつかの助けを使用することができます。このメソッドはコンパイルされますが、私にoutOfBoundsありがとう！

Answer 1

このソリューションでは、（N + M）Oで実行されます：

static boolean has(int number, int[][] a) { 
    int row = 0; 
    int col = a[0].length - 1; 
    while (row < a.length && col >= 0) { 
     int n = a[row][col]; 
     if (n < number) { 
      row++; 
     } else if (n > number) { 
      col--; 
     } else { 
      return true; 
     } 
    } 
    return false; 
} 

Answer 2

あなたはOでこれを解決することができます（ログ（N）+ログ（M））最初にあなたがしている整数を含む行を検索します（列がソートされているので）バイナリ検索を使用したい場合は、別のバイナリ検索（行がソートされるため）を実行して、その行の整数の正確な位置を見つけます。