二分法-二维数组中的查找

在这里插入图片描述

求解代码

这道题因为每一行从左到右都是递增的，且每一列从上到下也都是递增的。

我们不难发现，左上角是最小值，右下角是最大值。

左下的元素大于它上方的元素，小于它右方的元素。

所以，我们可以以左下角为起点，如果它小于target，则往右移找更大的；

如果它大于target，则往上移找更小的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


public boolean Find (int target, int[][] array) {

		if(array.length==0||array[0].length==0){
			return false;
		}

		int n = array.length;
		int m = array[0].length;

		for(int i=n-1,j=0;i>=0&&j<m;){
			if(array[i][j]<target){
				j++;
			}else if(array[i][j]==target){
				return true;
			}else{
				i--;
			}
		}
		return false;
    }