面试题4: 二维数组中的查找

package cn.zxy.interview;

/**
 * 分析:
 * 如果根据固有思维, 将目标数与二维数组中间的数进行比较显然很困难, 于是选择与右上角的数比较
 * 步骤:
 * 1. 初始化行指针row=0, 列指针col=columns-1
 * 2. if(row, col)==target 结束
 * 3. if(row, col) > target 因为这个数是一列最上面的数, 如果连这个数都大于target, 那么这一列的数肯定都大于target, 所以
 *    剔除这一列, col--
 * 4. if(row, col) < target 因为这个数是一行最右边的数, 如果连这个数都小于target, 那么这一列的数肯定都小于target. 所以
 *    剔除这一行, row++
 */
public class A04_2DSearch {
    public static boolean TwoDimensionSearch(int[][] a, int rows, int columns, int target){
        boolean found = false;
        if (a == null || rows == 0 || columns == 0) return found;

        int row = 0;
        int col = columns - 1;
        while(row < rows && col >= 0){
            if (a[row][col] == target){
                found = true;
                return found;
            }else if(a[row][col] > target){
                col--;
            }else {
                row++;
            }
        }
        return found;
    }

    public static void main(String[] args) {
        int[][] a1 = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
        boolean found = TwoDimensionSearch(a1, 4, 4, 0);
        System.out.println(found);
    }

}