左から右、上から下にソートされた2D配列の数値を検索するにはどうすればよいですか?

algorithm multidimensional-array search
左から右、上から下にソートされた2D配列の数値を検索するにはどうすればよいですか?

私は最近、このインタビューの質問をされましたが、それに対する良い解決策が何であるか興味があります。

__
配列内のすべての数値が左から右、上から下に向かって昇順である2D配列が与えられているとします。

ターゲット番号が配列内にあるかどうかを検索して判別する最良の方法は何ですか?
__

今、私の最初の傾向は、データがソートされているため、バイナリ検索を利用することです。 O(log N)時間で数値が1行にあるかどうかを判断できます。 しかし、それは私を落とす2つの方向です。

私がうまくいくと思う別の解決策は、途中から始めることです。 中央の値がターゲットよりも小さい場合、中央からマトリックスの左の正方形部分にあることを確認できます。 次に、斜めに移動して再度チェックし、ターゲット番号に磨きをかけるまで、ターゲットが潜在的に含まれる可能性のある正方形のサイズを小さくします。

この問題を解決するためのアイデアはありますか?

配列の例:

左から右、上から下に並べ替えられます。

1  2  4  5  6
2  3  5  7  8
4  6  8  9  10
5  8  9  10 11

  86  87


ベストアンサー

これが簡単なアプローチです:

  1. 左下隅から始めます。

  2. ターゲットがその値より小さい場合、それは私たちの上にあるに違いないので、* move
    ワンアップ*。

  3. そうしないと、ターゲットがその列に含まれないことがわかっているため、* move
    合ってるやつ*。

  4. 後藤2。

NxM`配列の場合、これは O(N + M) `で実行されます。 もっと良くするのは難しいと思います。 🙂

” ” ‘

*編集:*たくさんの良い議論。 上記の一般的なケースについて話していました。明らかに、「N」または「M」が小さい場合、バイナリ検索アプローチを使用して、対数時間に近い何かでこれを行うことができます。

好奇心those盛な人のための詳細を以下に示します。

歴史

この単純なアルゴリズムは、http://www.cs.geneseo.edu/~baldwin/math-thinking/saddleback.html [Saddleback Search]と呼ばれます。 しばらく前からあり、 `N == M`のときに最適です。 いくつかの参考文献:

  • デビッド・グリース、

  • https://rads.stackoverflow.com/amzn/click/com/0387964800 [The Science of Programming] *。 Springer-Verlag、1989

  • エドガー・ダイクストラ、

  • http://www.cs.utexas.edu/users/EWD/index09xx.html [The Saddleback Search] *。 注EWD-934、1985

ただし、「N <M」の場合、直観的にはバイナリ検索の方が「O(N + M)」よりも優れているはずであることが示唆されます。たとえば、「N == 1」の場合、純粋なバイナリ検索は対数で実行されます線形時間より。

最悪の場合

リチャードバードは、2006年の論文で、バイナリ検索がサドルバックアルゴリズムを改善できるというこの直感を検証しました。

  • リチャード・S 鳥、

  • http://www.cs.ox.ac.uk/publications/publication2664-abstract.html [Saddleback Searchの改善:アルゴリズム設計のレッスン] *、_ in Mathematics of Program Construction、pp。 82—​89、ボリューム4014、2006_。

かなり珍しい会話手法を使用して、Birdは「N ⇐ M」の場合、この問題には「Ω(N * log(M / N))」の下限があることを示しています。 これは、「N == M」の場合に線形パフォーマンスを、「N == 1」の場合に対数パフォーマンスを提供するため、理にかなっています。

長方形配列のアルゴリズム

行ごとのバイナリ検索を使用する1つのアプローチは次のようになります。

  1. `N <M`の長方形配列から始めます。 「N」は行だとしましょう
    「M」は列です。

  2. `value`の中央の行でバイナリ検索を実行します。 見つかったら、
    行った。

  3. それ以外の場合、隣接する数字のペア s`と g`が見つかりました。
    s <値<g

  4. `s`の上と左の数字の長方形は
    「値」なので、削除できます。

  5. 「g」の下と右の長方形は「value」よりも大きく、
    それを排除することができます。

  6. 残りの2つの長方形のそれぞれについて、ステップ(2)に進みます。

最悪の場合の複雑さの観点から、このアルゴリズムは可能な解決策の半分を排除するために「log(M)」機能を実行し、2つの小さな問題で再帰的に自身を2回呼び出します。 `log(M)`のより小さなバージョンを行ごとに繰り返す必要がありますが、行の数が列の数に比べて少ない場合は、対数の時間でそれらの列をすべて削除できます価値があるように*。

これにより、アルゴリズムに「T(N、M)= log(M)+ 2 * T(M / 2、N / 2)」の複雑さが与えられ、Birdは「O(N * log(M / N)」 ) `。

Craig Gidneyが投稿した別のアプローチは、上記のアプローチに似たアルゴリズムを説明しています。「M / N`。 彼の分析によると、これにより「O(N * log(M / N))」のパフォーマンスも得られます。

性能比較

Big-O分析はすべてうまく機能していますが、これらのアプローチは実際にどの程度機能していますか? 以下のチャートは、ますます「正方形」配列の4つのアルゴリズムを調べています。

image:https://i.stack.imgur.com/SZwvl.png [アルゴリズムのパフォーマンスと直角度]

(「単純な」アルゴリズムは、配列のすべての要素を単純に検索します。 「再帰」アルゴリズムについては上記で説明しています。 「ハイブリッド」アルゴリズムは、http://twistedoakstudios.com/blog/Post5365_searching-a-sorted-matrix-faster [Gidney’s algorithm]の実装です。 各アレイサイズについて、ランダムに生成された1,000,000個の固定セットのセットで各アルゴリズムのタイミングを測定することにより、パフォーマンスを測定しました。

いくつかの注目すべき点:

  • 予想どおり、「バイナリ検索」アルゴリズムは最高のパフォーマンスを提供します
    長方形配列では、サドルバックアルゴリズムは正方形配列で最適に機能します。

  • サドルバックアルゴリズムは、「単純な」アルゴリズムよりもパフォーマンスが悪い
    おそらく各アイテムで複数の比較を行うため、1次元配列。

  • 「バイナリ検索」アルゴリズムが二乗するパフォーマンスヒット
    配列は、おそらくバイナリ検索を繰り返し実行するオーバーヘッドによるものです。

概要

バイナリ検索の賢明な使用は、長方形配列と正方形配列の両方に対して `O(N * log(M / N)`パフォーマンスを提供できます。 「O(N + M)」「サドルバック」アルゴリズムははるかに単純ですが、配列がますます長方形になるにつれてパフォーマンスが低下します。

104


この問題は `Θ(b lg(t))`時間を要します。ここで、 `b = min(w、h)`と `t = b / max(w、h)`です。 このソリューションについては、http://twistedoakstudios.com/blog/Post5365_searching-a-sorted-matrix-faster [このブログ投稿]で説明しています。

下限

敵は、アルゴリズムを強制的に `Ω(b lg(t))`クエリを作成することができます。これは、それ自体をメインの対角線に制限することによって行います。

image:https://i.stack.imgur.com/Pa5gX.gif [主対角線を使用した敵]

_凡例:白いセルは小さいアイテム、灰色のセルは大きいアイテム、黄色のセルは小さいか等しいアイテム、オレンジのセルは大きいか等しいアイテムです。 攻撃者は、アルゴリズムが最後に照会する黄色またはオレンジのセルのいずれかになるようにソリューションを強制します。

サイズが「t」の「b」独立ソートリストがあり、「Ω(b lg(t))」クエリを完全に排除する必要があることに注意してください。

アルゴリズム

  1. (一般性を失うことなく、「w> = h」と仮定します)

  2. ターゲット項目を上部の左にあるセル「t」と比較します
    有効な領域の右隅

    • セルのアイテムが一致する場合、現在の位置を返します。

    • セルのアイテムがターゲットアイテムよりも小さい場合は、
      バイナリ検索で行の残りの「t」セル。 これを行っている間に一致するアイテムが見つかった場合、その位置で戻ります。

    • そうでない場合、セルのアイテムはターゲットアイテムよりも多く、
      「t」の短い列。

  3. 有効な領域が残っていない場合は、失敗を返します

  4. 後藤ステップ2

アイテムを見つける:

image:https://i.stack.imgur.com/5iiKZ.gif [アイテムの検索]

アイテムが存在しないと判断する:

image:https://i.stack.imgur.com/eBJDe.gif [アイテムが存在しないと判断する]

凡例:白いセルは小さいアイテム、灰色のセルは大きいアイテム、緑色のセルは等しいアイテムです。

分析

削除する `b * t`短い列があります。 削除する長い行があります。 長い行を削除するには、「O(lg(t))」時間がかかります。 「t」の短い列を削除するには、「O(1)」時間がかかります。

最悪の場合、すべての列とすべての行を削除する必要があり、時間は `O(lg(t)* b + b * t * 1 / t)= O(b lg(t))`です。

私は lg`が1を超える結果にクランプすると仮定していることに注意してください(つまり、 `lg(x)= log_2(max(2、x)))。 そのため、「t = 1」を意味する「w = h」の場合、「O(b lg(1))= O(b)= O(w + h)」の予想される境界が得られます。

コード

public static Tuple TryFindItemInSortedMatrix(this IReadOnlyList> grid, T item, IComparer comparer = null) {
    if (grid == null) throw new ArgumentNullException("grid");
    comparer = comparer ?? Comparer.Default;

    // check size
    var width = grid.Count;
    if (width == 0) return null;
    var height = grid[0].Count;
    if (height < width) {
        var result = grid.LazyTranspose().TryFindItemInSortedMatrix(item, comparer);
        if (result == null) return null;
        return Tuple.Create(result.Item2, result.Item1);
    }

    // search
    var minCol = 0;
    var maxRow = height - 1;
    var t = height / width;
    while (minCol < width && maxRow >= 0) {
        // query the item in the minimum column, t above the maximum row
        var luckyRow = Math.Max(maxRow - t, 0);
        var cmpItemVsLucky = comparer.Compare(item, grid[minCol][luckyRow]);
        if (cmpItemVsLucky == 0) return Tuple.Create(minCol, luckyRow);

        // did we eliminate t rows from the bottom?
        if (cmpItemVsLucky < 0) {
            maxRow = luckyRow - 1;
            continue;
        }

        // we eliminated most of the current minimum column
        // spend lg(t) time eliminating rest of column
        var minRowInCol = luckyRow + 1;
        var maxRowInCol = maxRow;
        while (minRowInCol <= maxRowInCol) {
            var mid = minRowInCol + (maxRowInCol - minRowInCol + 1) / 2;
            var cmpItemVsMid = comparer.Compare(item, grid[minCol][mid]);
            if (cmpItemVsMid == 0) return Tuple.Create(minCol, mid);
            if (cmpItemVsMid > 0) {
                minRowInCol = mid + 1;
            } else {
                maxRowInCol = mid - 1;
                maxRow = mid - 1;
            }
        }

        minCol += 1;
    }

    return null;
}

32


この問題には、あなたが提案したものと同様の分割統治戦略を使用しますが、詳細は少し異なります。

これは、マトリックスの部分範囲での再帰検索になります。

各ステップで、範囲の中央にある要素を選択します。 見つかった値が探しているものであれば、これで完了です。

そうではなく、見つかった値が探している値よりも小さい場合、現在の位置の左上の象限にないことがわかります。 したがって、2つのサブ範囲を再帰的に検索します。現在の位置より下のすべて(排他的)と、現在の位置以上の右のすべて(排他的)です。

それ以外の場合(見つかった値は探している値よりも大きい)、現在の位置の右下の象限にないことがわかります。 したがって、2つのサブ範囲を再帰的に検索します。現在の位置の左側にあるすべて(排他的)、および現在の列または右側の列にある現在の位置の上のすべて(排他的)です。

そしてバダビン、あなたはそれを見つけました。

各再帰呼び出しは、現在のサブレンジのみを処理し、(たとえば)現在の位置より上のすべての行を処理しないことに注意してください。 現在のサブレンジ内のもののみ。

擬似コードは次のとおりです。

bool numberSearch(int[][] arr, int value, int minX, int maxX, int minY, int maxY)

if (minX == maxX and minY == maxY and arr[minX,minY] != value)
    return false
if (arr[minX,minY] > value) return false;  // Early exits if the value can't be in
if (arr[maxX,maxY] < value) return false;  // this subrange at all.
int nextX = (minX + maxX) / 2
int nextY = (minY + maxY) / 2
if (arr[nextX,nextY] == value)
{
    print nextX,nextY
    return true
}
else if (arr[nextX,nextY] < value)
{
    if (numberSearch(arr, value, minX, maxX, nextY + 1, maxY))
        return true
    return numberSearch(arr, value, nextX + 1, maxX, minY, nextY)
}
else
{
    if (numberSearch(arr, value, minX, nextX - 1, minY, maxY))
        return true
    reutrn numberSearch(arr, value, nextX, maxX, minY, nextY)
}

17


これまでの主な2つの答えは、おそらく「O(log N)」「ZigZagメソッド」と「O(N + M)」バイナリ検索メソッドのようです。 2つの方法をいくつかのさまざまなセットアップと比較して、テストを行うと思いました。 詳細は以下のとおりです。

配列はすべてのテストでN x Nの正方形で、Nは125から8000まで変化します(私のJVMヒープが処理できる最大)。 配列のサイズごとに、配列内のランダムな場所を選んで1つの「2」を配置しました。 次に、可能な場所(2の右と下)に「3」を配置し、残りの配列を「1」で埋めました。 初期のコメンターの一部は、このタイプのセットアップは両方のアルゴリズムの最悪の実行時間をもたらすと考えているようでした。 配列サイズごとに、2(検索ターゲット)に対して100個の異なるランダムな場所を選択し、テストを実行しました。 各アルゴリズムの平均実行時間と最悪の場合の実行時間を記録しました。 Javaで適切なmsの読み取り値を取得するには速すぎて、JavaのnanoTime()を信用していないため、常に一定のバイアス係数を追加するために各テストを1000回繰り返しました。 結果は次のとおりです。

image:https://i.imgur.com/4Y8eyPy.png [ここに画像の説明を入力]

ZigZagは、平均および最悪の両方のケースで、すべてのテストでバイナリを破りましたが、それらはすべて、互いに多少の差があります。

これがJavaコードです。

public class SearchSortedArray2D {

    static boolean findZigZag(int[][] a, int t) {
        int i = 0;
        int j = a.length - 1;
        while (i <= a.length - 1 && j >= 0) {
            if (a[i][j] == t) return true;
            else if (a[i][j] < t) i++;
            else j--;
        }
        return false;
    }

    static boolean findBinarySearch(int[][] a, int t) {
        return findBinarySearch(a, t, 0, 0, a.length - 1, a.length - 1);
    }

    static boolean findBinarySearch(int[][] a, int t,
            int r1, int c1, int r2, int c2) {
        if (r1 > r2 || c1 > c2) return false;
        if (r1 == r2 && c1 == c2 && a[r1][c1] != t) return false;
        if (a[r1][c1] > t) return false;
        if (a[r2][c2] < t) return false;

        int rm = (r1 + r2) / 2;
        int cm = (c1 + c2) / 2;
        if (a[rm][cm] == t) return true;
        else if (a[rm][cm] > t) {
            boolean b1 = findBinarySearch(a, t, r1, c1, r2, cm - 1);
            boolean b2 = findBinarySearch(a, t, r1, cm, rm - 1, c2);
            return (b1 || b2);
        } else {
            boolean b1 = findBinarySearch(a, t, r1, cm + 1, rm, c2);
            boolean b2 = findBinarySearch(a, t, rm + 1, c1, r2, c2);
            return (b1 || b2);
        }
    }

    static void randomizeArray(int[][] a, int N) {
        int ri = (int) (Math.random() * N);
        int rj = (int) (Math.random() * N);
        a[ri][rj] = 2;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == ri && j == rj) continue;
                else if (i > ri || j > rj) a[i][j] = 3;
                else a[i][j] = 1;
            }
        }
    }

    public static void main(String[] args) {

        int N = 8000;
        int[][] a = new int[N][N];
        int randoms = 100;
        int repeats = 1000;

        long start, end, duration;
        long zigMin = Integer.MAX_VALUE, zigMax = Integer.MIN_VALUE;
        long binMin = Integer.MAX_VALUE, binMax = Integer.MIN_VALUE;
        long zigSum = 0, zigAvg;
        long binSum = 0, binAvg;

        for (int k = 0; k < randoms; k++) {
            randomizeArray(a, N);

            start = System.currentTimeMillis();
            for (int i = 0; i < repeats; i++) findZigZag(a, 2);
            end = System.currentTimeMillis();
            duration = end - start;
            zigSum += duration;
            zigMin = Math.min(zigMin, duration);
            zigMax = Math.max(zigMax, duration);

            start = System.currentTimeMillis();
            for (int i = 0; i < repeats; i++) findBinarySearch(a, 2);
            end = System.currentTimeMillis();
            duration = end - start;
            binSum += duration;
            binMin = Math.min(binMin, duration);
            binMax = Math.max(binMax, duration);
        }
        zigAvg = zigSum / randoms;
        binAvg = binSum / randoms;

        System.out.println(findZigZag(a, 2) ?
                "Found via zigzag method. " : "ERROR. ");
        //System.out.println("min search time: " + zigMin + "ms");
        System.out.println("max search time: " + zigMax + "ms");
        System.out.println("avg search time: " + zigAvg + "ms");

        System.out.println();

        System.out.println(findBinarySearch(a, 2) ?
                "Found via binary search method. " : "ERROR. ");
        //System.out.println("min search time: " + binMin + "ms");
        System.out.println("max search time: " + binMax + "ms");
        System.out.println("avg search time: " + binAvg + "ms");
    }
}

6


これは、問題の下限の簡単な証明です。

線形時間(要素の数ではなく、配列の次元)を超えることはできません。 以下の配列では、「*」とマークされた各要素は5または6のいずれかです(他の要素とは無関係)。 したがって、ターゲット値が6(または5)の場合、アルゴリズムはそれらすべてを調べる必要があります。

1 2 3 4 *
2 3 4 * 7
3 4 * 7 8
4 * 7 8 9
* 7 8 9 10

もちろん、これはより大きな配列にも拡張されます。 これは、https://stackoverflow.com/questions/2457792/given-a-2d-array-sorted-in-increasing-order-from-left-to-right-and-top-to-bottom/2458113#2458113 [この答え]が最適です。

更新:Jeffrey L Whitledgeが指摘したように、実行時間と入力データサイズの漸近的な下限としてのみ最適です(単一の変数として扱われます)。 両方の配列次元で2変数関数として扱われる実行時間を改善できます。

5


私はここが答えだと思います

bool findNum(int arr[][ARR_MAX],int xmin, int xmax, int ymin,int ymax,int key)
{
    if (xmin > xmax || ymin > ymax || xmax < xmin || ymax < ymin) return false;
    if ((xmin == xmax) && (ymin == ymax) && (arr[xmin][ymin] != key)) return false;
    if (arr[xmin][ymin] > key || arr[xmax][ymax] < key) return false;
    if (arr[xmin][ymin] == key || arr[xmax][ymax] == key) return true;

    int xnew = (xmin + xmax)/2;
    int ynew = (ymin + ymax)/2;

    if (arr[xnew][ynew] == key) return true;
    if (arr[xnew][ynew] < key)
    {
        if (findNum(arr,xnew+1,xmax,ymin,ymax,key))
            return true;
        return (findNum(arr,xmin,xmax,ynew+1,ymax,key));
    } else {
        if (findNum(arr,xmin,xnew-1,ymin,ymax,key))
            return true;
        return (findNum(arr,xmin,xmax,ymin,ynew-1,key));
    }
}

4


興味深い質問です。 この考えを考慮してください。すべての数値がターゲットよりも大きい境界と、すべての数値がターゲットよりも小さい境界を作成します。 2つの間に何かが残っている場合、それがターゲットです。

あなたの例で3を探している場合、4に達するまで最初の行を読んでから、3より大きい最小の隣接番号(対角線を含む)を探します。

1 2 * 4 * 5 6 + 2 3 * 5 * 7 8 + * 4 6 * 8 9 10 + 5 8 9 10 11

今、私は3未満のそれらの番号についても同じことをします。

1 * 2 4 * 5 6 + * 2 * 3 * 5 * 7 8 + * 4 6 * 8 9 10 + 5 8 9 10 11

今、私は尋ねます、2つの境界内に何かありますか? はいの場合、3でなければなりません。 いいえの場合、3はありません。 私は実際に番号を見つけられないので、間接的なもののように、私はそれがそこにあるに違いないと推測します。 これには、3をすべてカウントするという追加のボーナスがあります。

いくつかの例でこれを試しましたが、うまくいくようです。

1


配列の対角線を通るバイナリ検索が最適なオプションです。 要素が対角線の要素以下かどうかを調べることができます。

1


  • O(M log(N))*解がMxN配列で問題ない場合-

template
struct MN * get(int a[][n], int k, int M, int N){
  struct MN *result = new MN;
  result->m = -1;
  result->n = -1;

  /* Do a binary search on each row since rows (and columns too) are sorted. */
  for(int i = 0; i < M; i++){
    int lo = 0; int hi = N - 1;
    while(lo <= hi){
      int mid = lo + (hi-lo)/2;
      if(k < a[i][mid]) hi = mid - 1;
      else if (k > a[i][mid]) lo = mid + 1;
      else{
        result->m = i;
        result->n = mid;
        return result;
      }
    }
  }
  return result;
}

これがうまくいかない場合、またはバグがある場合はお知らせください。

0


  1. ターゲット番号が存在する可能性のある行でバイナリ検索を実行します。

  2. グラフにする:常に最小の未訪問の近隣ノードを取得し、大きすぎる数が見つかった場合にバックトラックして、数を探します

0


タイトルとURLをコピーしました