这样的面试题，你会吗？——博文视点杯有奖答题活动

public static void main(String[] args) {
		int[][] param = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 },
				{ 6, 8, 11, 15 } };

		for (int i = 0; i < length; i++) {
			int[] temp = param[i];
			boolean f = findKey(temp, 6);
			if (f) {
				System.out.println("Found Key");
				break;
			}
		}
	}
	public static boolean findKey(int[] temp, int searchKey) {
		int lowerBound = 0;
		int upperBound = temp.length - 1;
		int curIn;
		while (true) {
			curIn = (lowerBound + upperBound) / 2;
			if (temp[curIn] == searchKey)
				return true;
			else if (lowerBound > upperBound) {
				return false;
			} else {
				if (temp[curIn] < searchKey)
					lowerBound = curIn + 1;
				else
					upperBound = curIn - 1;
			}
		}
	}

 第一题是这样的吗？数据很少 二分法的优势体现不出来

这样的题目几年前就玩剩下的了。

这样的话几年前就说剩下了。

虽然不知道你在讲什么，但是感觉很牛的样子

第一题给个思路：
对于图中任意一个数，可以证明，以这个数为原点，左上区域（第二象限）的数字必然比这个数小，右下区域（第四象限）的数字必然比这个数字大。注意这个区域可以是长方形，是以原点开始一直到图形边界的整个矩形区域。我们可以基于这个性质设计算法。

对于刚好是正方形的图形，显然可以直接在对角线上进行二分法查找（设要找的数字是x），如果没有找到结果，也可以定位到一对数a[i，j]和a[i+1，j+1]，使得a[i，j]＜x＜a[i+1，j+1]，x不可能出现在以a[i，j]为右下角一直到整个图形边界的那片区域，因为其中的数字都比a[i，j]小。同理，也不可能出现在以a[i+1，j+1]为左上角的那片区域。这样一下子就去掉了至少一半的候选数，剩下右上和左下两片区域。

现在对这两个矩形区域继续分别重复进行上面的步骤就可以了，问题是剩下的矩形很可能是长方形。当然继续从左上角开始找对角也是可以的，但这样的话一次最多只能消去边长为短边长度的正方形区域。为了尽量让对角线通过矩形中心，我们可以在长边上的（长边长度-短边长度）\2 的位置上开始取对角线进行二分查找。如果未找到，继续消去这个子区域的左上和右下区域，重复这个步骤直到找出结果。

由于每次查找后都会留下右上和左下两个矩形区域，需要用一个栈来记录。也就是，每次对角二分查找完后，右上和左下两个矩形区域的边界数据入栈，然后弹出栈顶的一个区域继续查，直到区域只包含一个数字就不用入栈了。

可以证明，当区域的短边为1时（矩阵退化为数列），上面的算法等价于数列上的二分查找。

青蛙跳不就是山寨版的凑硬币吗？用m种面值的硬币凑出n元有多少种搞法。

解题关键是：凑出金额a的总方案数= 不用某种面值为d的硬币来凑出a的方案数 + 用所有硬币凑出金额a-d的方案数。

题目2a相当于用1元和两元硬币凑出n元

凑出n元的方案数=只用1元来凑n元的方案数（只有1种） + 用两种硬币凑出n-2元的方案数

用两种硬币凑出n-2元的方案数 = 只用1元的方案数+ 用两种硬币凑n-4元的方案数。

••••••
用两种硬币凑出0元的方案是1
用两种硬币凑出-1元的方案数是0

其实这些问题网上都是可以找到答案的，我只告诉第二题的答案：（我自己思考的，正确性待定）

       | 1 (假设n阶，一次跳n阶，即n= n-n = 0）
f(n) = | 1（n=1）
       | 2*f(n-1) (n>=2)


不信的可以自己尝试。

第二题没太搞明白，也想不出来太高效的算法，只做出来第一题。因为肯定拿不到奖品了，就在这里说一下我的思路。
我的思路基本上还是二分法查找。把数组看成一个二维表，首先判断数字是否小于左上角大于右下角，超范围则肯定不在数组中。然后沿着左上角到右下角的这条斜线进行二分查找。如果正好在这条线上，最好。如果不在，则查那个点的值大于这个数，而这个点左上方的值小于这个数。则数字有存在于该点向上和向左的两条线上。对这两条线分别进行二分查找，就可以确定是否存在这个数了。

  public boolean isArrayData(int num) {
	int arr[][] = new int[][] { { 1, 2, 8, 9 }, { 2, 4, 9, 12 },
		{ 4, 7, 10, 13 }, { 6, 8, 11, 15 } };
	int columnNum = 0;
	for (int i = 0; i < arr.length; i++) {
	       if (arr[i][0] > num) {
		return false;
	       }
                      if (columnNum == 0) columnNum = arr[i].length;
	        for (int j = 0; j < columnNum; j++) {
		if (arr[i][j] > num) {
		    columnNum = j;
		} else if (arr[i][j] == num) {

		    return true;
		}
	         }
	  }
	return false;
    }

 给个我的答案呵

恩，确实是书买不出去了
public class SndArrayFind {
public static void main(String[] args){
int[][] array = new int[4][4];
array[0][0] = 1;
array[0][1] = 2;
array[0][2] = 8;
array[0][3] = 9;

array[1][0] = 2;
array[1][1] = 4;
array[1][2] = 9;
array[1][3] = 12;

array[2][0] = 4;
array[2][1] = 7;
array[2][2] = 10;
array[2][3] = 13;

array[3][0] = 6;
array[3][1] = 8;
array[3][2] = 11;
array[3][3] = 15;

//未找到的数据
System.out.println(find(array,0));
System.out.println(find(array,5));
System.out.println(find(array,14));
System.out.println(find(array,16));

//已找到的数据
System.out.println(find(array,1));
System.out.println(find(array,7));
System.out.println(find(array,9));
System.out.println(find(array,15));
}

/**按照递增方式查找，递减同理（就不列了）**/
public static boolean find(int[][] array,int findNum){
int column = getFirstRow(array[0],findNum);
if(column==-1){ //表示所有的数都大于findNum
// System.out.println("未找到，行"+0+",列"+column);
return false;
}else if(array[0][column]==findNum){
// System.out.println("已找到，行"+0+",列"+column);
return true;
}else{
return find(array,findNum,1,column);
}
}

public static boolean find(int[][] array,int findNum,int row,int column){
if(row>=array.length){ //没有该列
// System.out.println("未找到，行"+row+",列"+column);
return false;
}
if(column==-1){ //没有该行
// System.out.println("未找到，行"+row+",列"+column);
return false;
}
if(array[row][column]==findNum){ //等于则找到
// System.out.println("已找到，行"+row+",列"+column);
return true;
}else if(array[row][column]>findNum){ //大于往左
return find(array,findNum,row,column-1);
}else{ //小于往下
return find(array,findNum,row+1,column);
}
}

public static int getFirstRow(int[] array,int findNum){
for(int i=0;i<array.length;i++){
int num = array[i];
if(num>findNum){ //如果标识num[i]>findNum则返回i-1;
return i-1;
}
}
return array.length-1;
}
}