二维数组中的查找

题目描述：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数

思路描述：一个数字的下方和右方是比它本身大的区域，而左方和上方时比它本身小的区域。选取右上角的数字进行比较，当该数大于指定的数时，舍去该列，当该数小于指定的数时，舍去该行，当相等时，则表示找到

C语言实现：

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

typedef unsigned int boolean;
#define MAX 4
#define TRUE  1
#define FALSE -1

void showAry(int ary[MAX][MAX]);
boolean find(int ary[MAX][MAX], int rows, int cols, int number);

void showAry(int ary[MAX][MAX]) {
    int i = 0, j = 0;
    for(; i < MAX; i++) {
        j = 0;
        for(; j < MAX; j++) {
            printf("%d ", ary[i][j]);
        }
    }
}

boolean find(int ary[MAX][MAX], int rows, int cols, int number) {
    int i = 0, 
        j = cols - 1,
        n = 0;
    boolean result = FALSE;
    
    if(ary == NULL || rows <= 0 || cols <= 0) {
        return result;
    }
    
    while(i < rows && j >= 0) {
        n = ary[i][j];
        if(number == n) {
            printf("\nary[%d, %d] = %d\n", i, j, n);
            result = TRUE;
            break;  
        }else if(number < n) {
            j -= 1; 
        }else if(number > n) {
            i += 1;
        }
    }
    return result;
}

//1 2 8 9 2 4 9 12 4 7 10 13 6 8 11 15
int main() {
    int ary[MAX][MAX];
    int i = 0, j = 0;
    
    for(; i < MAX; i++) {
        j = 0;
        for(; j < MAX; j++) {
            scanf("%d", &ary[i][j]);
        }
    }
    showAry(ary);
    find(ary, MAX, MAX, 7);
}

Java实现：

import java.util.Scanner;

public class FindInArray {
    private int [][]ary;
    
    public FindInArray(int [][]ary) {
        this.ary = ary;
    }
    
    public boolean find(int rows, int cols, int target) {
            int i = 0, 
                j = cols - 1,
                n = 0;
            boolean result = false;
            
            if(ary == null || rows <= 0 || cols <= 0) {
                return result;
            }
            
            while(i < rows && j >= 0) {
                n = ary[i][j];
                if(target == n) {
                    System.out.println("ary["+ i + "]" + "[" + j + "] = " + ary[i][j]);
                    result = true;
                    break;  
                }else if(target < n) {
                    j -= 1; 
                }else if(target > n) {
                    i += 1;
                }
            }
            return result;
    }

    public static void main(String[] args) {
        int [][]ary = new int[4][4];
        int i, j;
        Scanner input = new Scanner(System.in);
        
        for(i = 0; i < 4; i++)  {
            j = 0;
            for(j = 0; j < 4; j++) {
                ary[i][j] = input.nextInt();
            }
        }       
        
        for(i = 0; i < 4; i++) {
            for(j = 0; j < 4; j++) {
                System.out.println(ary[i][j]);
            }
        }
        
        FindInArray instance = new FindInArray(ary);
        instance.find(4, 4, 7);
    }
}