/*
 * 二维数组从左到右，从上到下递增
 * 查找输入的数，效率尽可能高
 * 思路：从右上角或左下角开始查找
 */
import java.util.Scanner;

public class findTarget {
	public static boolean find(int [][]a,int rows,int cols,int target){
		boolean found=false;
		int count=0;//移动次数
		if(a!=null){
			int row=0;
			int col=cols-1;
			while(row<rows && col>=0){
				if(a[row][col]== target){
					found=true;
					break;
				}
				else if(a[row][col]>target){
					col--;
					count++;
				}
				else{
					row++;
					count++;
				}
			}
			System.out.println("Move "+count+" times");
		}
		
		return found;
	}
	public static void main(String[] args) {
		int [][]a={ {1,2,8,9},{2,4,9,12},
					{4,7,10,13},{6,8,11,15}};
		//也可以用一维数组实现
		System.out.println("Input the terget number:");
		Scanner cin=new Scanner(System.in);
		int k=cin.nextInt();
		
		if(find(a,a.length,a[0].length,k)){
			System.out.println("Yes");
		}
		else{
			System.out.println("NO");
		}
	}

}
/* Test output
Input the terget number:
7
Move 4 times
Yes*/