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

• 2019 年 11 月 8 日
• 笔记

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/shiliang97/article/details/101649068

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

问题代码

class Solution {  public:      bool Find(int target, vector<vector<int> > array) {          int a=array.size();          int b=array[0].size();          if(b==0){              return false;          }          int maxx=a-1,maxy=b-1,minx=0,miny=0;          while(array[(maxx+minx)/2][(miny+maxy)/2]!=target&&!(maxx!=minx||maxy!=miny)){              if(array[(maxx+minx)/2][(miny+maxy)/2]>target){                  maxx=(maxx+minx)/2;                  maxy=(maxy+miny)/2;              }else if(array[(maxx+minx)/2][(miny+maxy)/2]>target){                  minx=(maxx+minx)/2;                  miny=(maxy+miny)/2;              }else{                   return true;              }              if(array[(maxx+minx)/2-1][(miny+maxy)/2]==target||array[(maxx+minx)/2][(miny+maxy)/2-1]==target){                  return true;              }          }          if(array[(maxx+minx)/2][(miny+maxy)/2]==target){              return true;          }          return false;      }  };

遍历就能过。。我非要想一个好的。。。我再课下想想吧~

AC代码

class Solution {  public:      bool Find(int target, vector<vector<int> > array) {          int Wide_size = array.size();          int Long_size = array[0].size();          int i;          int j;            for (i = 0;i<Wide_size; i++)          {              for (j = 0; j < Long_size; j++)              {                  if (target == array[i][j])                  {                      return true;                  }              }          }          return false;      }  };