二维数组中查找某个值

题目大意：

  在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
如：
给定的二维数组：
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
查找数字7，返回true，查找数字5，返回false.

解题思路：

  由题意可知，二维数组是有序的，由此想到必须利用到这个特性。通过观察发现，若我们选取数组右上角的数字作为查找的起始点，如果等于目标值，则直接返回true；否则：如果大于目标值，则在该列左侧进行查找，如果小于目标值，则在该行下方进行查找。这样重复迭代，每查找一次就缩小查找范围，直到找到要查找的数字，或者查找范围为空。

代码实现（java）：

/**
 * @author lm
 * @create 2018-03-27 17:20
 * @desc 在二维有序数组中查找某个目标值，有则返回true，否则返回false。
 **/
public class SearchingInTwoArr {

    public boolean find(int[][] arr, int target) {

        if (arr == null)  return false;
        //定义右上角位置
        int col = arr[0].length - 1;
        int row = 0;
       while (row < arr.length && col >= 0) {
           if (arr[row][col] == target) {
               return true;
           }else if (arr[row][col] > target) {
               col--;
           }else {
               row++;
           }
       }
       return false;
    }
}
//测试用例
public class SearchingInTwoArrTest {
    SearchingInTwoArr searchingInTwoArr = new SearchingInTwoArr();
    int [][] arr = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
    int target2 = 5;
    int target1 = 7;

    @Test
    public void find() throws Exception {


        assertEquals(true, searchingInTwoArr.find(arr, target1));
        assertEquals(false, searchingInTwoArr.find(arr, target2));
    }

}

总结：

  同理可以从左下角开始进行查找。