剣指Offer-9度1384-2 D配列の検索

 Offer-9 1384-2 D の 
2013-11-23 23:23

タイトルの説明:
2 D配列では、各行が左から右に増加し、各列が上から下に増加した順にソートされます.関数を完了し、このような2次元配列と整数を入力して、配列にその整数が含まれているかどうかを判断してください.
入力:
入力には、各テストケースについて、複数のテストケースが含まれる場合があります.
入力される第1の動作の2つの整数mおよびn(1<=m,n<=1000):入力するマトリクスの行数および列数を表す.
入力された2行目には、検索する数値を表す整数t(1<=t<=1000000)が含まれます.
次のm行は、各行にn個の数があり、問題が与えるm行n列を表す行列(行列は、問題記述に示すように、各行が左から右に増加する順序で並べ替えられ、各列が上から下に増加する順序で並べ替えられる.
出力:
各テストケースに対応し、
出力「Yes」は、2次元配列で数値tが見つかったことを表します.
出力「No」は、2次元配列に数字tが見つからないことを表す.
サンプル入力:

3 3

5

1 2 3

4 5 6

7 8 9

3 3

1

2 3 4

5 6 7

8 9 10

3 3

12

2 3 4

5 6 7

8 9 10

サンプル出力:

Yes

No

No

 ：
　　 。 、 ， ，a[i][j] = a[i * col + j]，row ，col 。
　　 ， 。 O(log(m * n))， O(1)。

 1 // 650233    zhuli19901106    1384    Accepted     case     4968KB    813B    690MS

 2 // 201311121726

 3 #include <cstdio>

 4 using namespace std;

 5 

 6 const int MAXN = 1005;

 7 int a[MAXN][MAXN];

 8 int x, y;

 9 

10 int main()

11 {

12     int i, j;

13     int left, right, mid;

14     int target;

15     

16     while(scanf("%d%d", &x, &y) == 2){

17         scanf("%d", &target);

18         for(i = 0; i < x; ++i){

19             for(j = 0; j < y; ++j){

20                 scanf("%d", &a[i][j]);

21             }

22         }

23         if(x * y <= 0){

24             printf("No
");

25             continue;

26         }

27         left = 0;

28         right = x * y - 1;

29         while(left <= right){

30             mid = (left + right) / 2;

31             i = mid / y;

32             j = mid % y;

33             if(target < a[i][j]){

34                 right = mid - 1;

35             }else if(target > a[i][j]){

36                 left = mid + 1;

37             }else{

38                 break;

39             }

40         }

41         

42         printf((left <= right) ? "Yes
" : "No
");

43     }

44     

45     return 0;

46 }