ソートされた二次元配列の効率のいい探索法

Question

全ての行について左から右へ昇順に、かつ全ての列について上から下へ昇順にソートされた二次元配列A[n][m]があったとして、ある値を入力したときにそれに一致する要素番号A(i,j)を取得するプログラムをCで実行したいのですが、できるだけ効率のよいアルゴリズムが思いつきません。

一次元配列では二分探索により要素の特定ができましたが、Cでは二次元配列のある行だけを関数の引数として渡すことができないため他にいい方法がないか…と悩んでいます。

単純にすべての要素を調べつくした場合のO(n*m)よりも早く実装できるアルゴリズムはありますでしょうか？

二次元配列の全ての要素は正整数で、該当する要素が複数あった場合は全ての要素番号を探索します。

Comments

[kazuma-s]

n=3, m=4 で
1 2 4 7
2 3 5 8
3 4 6 9
のように同じ値の要素があった場合、
どの要素番号を取得するのでしょうか？

[Zuishin]

第一行でバイナリサーチし、目標の値を越えない最大のものをみつけます。そうすると、そこより右のデータに目標の値は含まれないので、それより右の列を探索範囲から外すことができます。

同様に左、上、下も削って探索範囲をせまくできます。

これを探索範囲が小さくならなくなるまで繰り返して残りを全探索でどうでしょうか。

[Hinomae]

同じ値が存在し、それが探索したい値の場合は該当する要素番号をすべて取得します。
Zuishinさんのアルゴリズムの説明を理解しきっていないのですが、kazuma-sさんが提示したように複数存在する場合も実行できますでしょうか？

[vdxYxFhemyW4EGX]

.

[vdxYxFhemyW4EGX]

コースのラインに質問してくだされば、簡単なアイデアは提供しますから、そちらをみて考えてみてはどうですか。

Answer 1

横方向indexをx, 縦方向indexをyと記すとき，
(x,y)=(x_,y_)の要素を調べれば

• x<=x_ 且つ y<=y_ な領域
• x>=x_ 且つ y>=y_ な領域

の少なくとも一つを探索領域から除外できる，という話に見えるので，
四角い領域をざくざくと切り捨てていくことができるんじゃないかな，とか…
（e.g. とりあえず初手で真ん中ら辺の要素を調べれば全体の1/4を除外できる）

各ステップでの最も効率が良い(x_,y_)の決定方法までは示せませんけど…
とりあえあず，初手を前記の(e.g.)として，残った 3/4 を３つの四角い領域だとして再帰的に繰り返せば全ての箇所を見つけることができると思う．

Answer 2

自分で考えましょう。以前にもしていたようですが、学校の課題をそのまま質問すると言うのはよくないと思いますよ。友達と議論してみてはいかがですか。

Comments

[Hinomae]

ご指摘ありがとうございます。
問題を解決するための知識を共有しあう場として存在しているこのようなサイトで解答へのヒントを得ようとすることと、友人とその問題について考え合うことは「問題を解く」というゴールに着目すればあまり本質的な違いはないと思いますが、今後はできるだけ友人と議論する機会を増やすのもいいかもしれないですね。

[vdxYxFhemyW4EGX]

たしかに目的は同じですね。しかし、知識量が豊富な方が多くいるこのサイトで質問するよりも、知識量が質問者様と同じくらいの友人と議論するというのでは、やはり思考しているかどうかというところに大きな差が出ると考えます。
レポート課題などでは成績なども大きく影響されますので、このような場を用いることは控えた方が良いかも知れないと思った次第です。唐突に失礼いたしました。

[fana]

低評価の理由：質問内容に対する「回答」とはなっていないと見えるので．Sorry．

[vdxYxFhemyW4EGX]

私はこのサイトに思い入れはないので大丈夫ですよ

Answer 3

二次元配列の二分探索、書いてみました。

#include <stdio.h>
#include <stdlib.h>

#define N 12
#define M 16

int mat[N][M] = {
  1,  5,  8, 10, 14, 16, 20, 23, 24, 26, 28, 31, 35, 38, 42, 46,
  8,  9, 12, 13, 15, 20, 21, 27, 29, 32, 35, 38, 42, 46, 50, 52,
 11, 14, 17, 19, 23, 25, 26, 31, 34, 36, 38, 40, 46, 47, 52, 55,
 16, 20, 23, 25, 28, 32, 33, 34, 36, 39, 42, 43, 48, 50, 54, 56,
 24, 25, 27, 30, 32, 34, 36, 37, 41, 44, 46, 49, 53, 56, 57, 61,
 31, 35, 36, 37, 40, 41, 42, 46, 50, 53, 57, 58, 59, 60, 61, 65,
 36, 39, 42, 45, 49, 53, 56, 59, 62, 66, 68, 70, 73, 75, 76, 77,
 41, 43, 44, 48, 51, 55, 58, 60, 66, 67, 70, 74, 76, 78, 82, 84,
 45, 47, 51, 55, 56, 58, 60, 63, 68, 71, 75, 79, 80, 81, 86, 87,
 51, 55, 59, 62, 63, 64, 68, 69, 71, 72, 79, 82, 84, 87, 91, 93,
 55, 59, 60, 63, 64, 66, 71, 73, 74, 77, 80, 83, 87, 91, 92, 97,
 59, 63, 65, 69, 70, 71, 75, 77, 78, 82, 86, 89, 91, 94, 98, 99,
};

void search(int v, int a, int b, int c, int d)
{
	if (a > b || c > d) return;
	int i = (a + b) / 2, j = (c + d) / 2;
	if (mat[i][j] > v) {
		search(v, a, i-1, c, d);
		search(v, i, b, c, j-1);
	}
	else if (mat[i][j] < v) {
		search(v, a, i, j+1, d);
		search(v, i+1, b, c, d);
	}
	else printf(" (%d,%d)", i, j);
}
	
int main(void)
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			printf("%3d", mat[i][j]);
		putchar('\n');
	}
	int v;
	while (printf(">> "), scanf("%d", &v) == 1) {
		search(v, 0, N-1, 0, M-1);
		putchar('\n');
	}
}

実行例

  1  5  8 10 14 16 20 23 24 26 28 31 35 38 42 46
  8  9 12 13 15 20 21 27 29 32 35 38 42 46 50 52
 11 14 17 19 23 25 26 31 34 36 38 40 46 47 52 55
 16 20 23 25 28 32 33 34 36 39 42 43 48 50 54 56
 24 25 27 30 32 34 36 37 41 44 46 49 53 56 57 61
 31 35 36 37 40 41 42 46 50 53 57 58 59 60 61 65
 36 39 42 45 49 53 56 59 62 66 68 70 73 75 76 77
 41 43 44 48 51 55 58 60 66 67 70 74 76 78 82 84
 45 47 51 55 56 58 60 63 68 71 75 79 80 81 86 87
 51 55 59 62 63 64 68 69 71 72 79 82 84 87 91 93
 55 59 60 63 64 66 71 73 74 77 80 83 87 91 92 97
 59 63 65 69 70 71 75 77 78 82 86 89 91 94 98 99
>> 1
 (0,0)
>> 99
 (11,15)
>> 50
 (1,14) (3,13) (5,8)
>> 18

>> 100

>> 37
 (4,7) (5,3)
>> .

Answer 4

重複が存在する場合も大して変わらないので、重複がないものとします。

位置を調べる値をTとした場合
i行目のT以下で最大の値がj列目に存在するとしたとき、i行j列目がTならそれを返す、そうでないならi+1行目のj列目から左にT以下の値が出てくるまで調べその値をjとし、i <- i + 1とし最初に戻る。というようにすれば、O(N + M)で見つけることができます。

重複がある場合にも基本的に同じ戦略が取れますが(T以下とT未満両方を調べるとその間がすべてTであるとわかる)、見つけるべき位置が最大でN * M個あるので、それを単純に列挙すると結局O(N * M)かかります。

Comments

[Hinomae]

この方法であればO(N+M)とより早く実装できそうです。
重複がある場合も答えて下さりありがとうございます。