二維數(shù)組中的查找

題目描述：

在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

輸入：

輸入可能包含多個(gè)測(cè)試樣例，對(duì)于每個(gè)測(cè)試案例，

輸入的第一行為兩個(gè)整數(shù)m和n(1<=m,n<=1000)：代表將要輸入的矩陣的行數(shù)和列數(shù)。

輸入的第二行包括一個(gè)整數(shù)t(1<=t<=1000000)：代表要查找的數(shù)字。

接下來(lái)的m行，每行有n個(gè)數(shù)，代表題目所給出的m行n列的矩陣(矩陣如題目描述所示，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。

輸出：

對(duì)應(yīng)每個(gè)測(cè)試案例，

輸出”Yes”代表在二維數(shù)組中找到了數(shù)字t。

輸出”No”代表在二維數(shù)組中沒(méi)有找到數(shù)字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
//
//  main.c
//  二維數(shù)組中的查找
//
//  Created by 李亞坤 on 14-9-27.
//  Copyright (c) 2014年 李亞坤. All rights reserved.
//

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

#define MAX 1000000

int find(int m, int n, int target,int a[])
{
    // 二分搞起了
    int middle, left, right;
    left = 0;
    right = m * n;
    
    while (left < right) {
        middle = (left + right - 1) / 2;
        if (target > a[middle]) {
            left = middle + 1;
        }
        else
            if (target < a[middle]) {
                right = middle;
            }
        else
            return 0;
    }

    return -1;
}



int main(int argc, const char * argv[]) {

    int a[MAX];
    int m, n;
    int i, j;
    int target;
    scanf("%d %d", &m, &n);
    
    scanf("%d", &target);
    
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &a[i * m + j]);
        }
    }

    if (find(m, n, target, a) == 0)
        printf("Yes
");
    else
        printf("No
");
    return 0;
}

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)