【剑指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;
    }
}

以上