【剑指offer】1、二维数组中的查找

【剑指offer】Java实现之二维数组中的查找。

题目描述：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
考察点：数组
视频题解地址：https://www.bilibili.com/video/bv1wz411B77T
思路：首先很明显暴力法是一种做法，强行遍历就完事了。

public class Solution {
    public boolean Find(int target, int [][] array) {
      for(int i=0;i<array.length;i++)
          for(int j=0;j<array[0].length;j++)
          {
              if (array[i][j]==target)
                  return true;
          }
    return false;
    }
}

接下来就是仿照一维数组中查找的优化方法，一维数组除了暴力法还能怎样，二分呗，这里也可以使用二分的方式。
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。这里有顺序存储结构以及有序排列，那我们只需要找到二分的方法即可。在什么位置可以将大小的比较抽象成二分呢。很显然，在左上和右下。

如图，从左下开始找就变成了，比target大就往上找，比target小就往右找，直到找到边界跳出循环输出false，中途找到就输出true。
代码如下：

import java.util.*;
public class Solution {
    public boolean Find(int target, int [][] array) {
        int rowSize=array.length;
        int colSize=array[0].length;
        int i,j;
        for (i=rowSize-1,j=0;j<colSize&&i>=0;){
            if (array[i][j]==target) {
                return true;
            }
            if (array[i][j]<target){
                j++;
                continue;
            }
            if (array[i][j]>target){
                i--;
                continue;
            }

        }
        return false;
    }
}

以上