• 👑专栏内容：剑指offer
• ⛪个人主页：子夜的星的主页
• 💕座右铭：前路未远，步履不停

目录

• 一、题目描述
• • 1、题目
  • 2、示例
  • • 示例Ⅰ
    • 示例Ⅱ
• 二、题目分析
• • 1、暴力法
  • 2、二分法
  • 3、利用题目特性
• 三、代码总结
• • 1、暴力法代码
  • 2、二分法代码
  • 3、利用特性

一、题目描述

1、题目

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

2、示例

示例Ⅰ

输入：7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：true
说明：存在7，返回true

示例Ⅱ

输入：3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：false
说明：不存在3，返回false

二、题目分析

1、暴力法

看见这道题的第一想法就是暴力法，通过两个循环，从二维数组的起始元素开始逐个遍历，如果当前元素等于目标值，则返回true，如果当前元素小于目标值，则继续遍历，如果遍历完所有元素还没有找到，就返回false。
我们使用C++语言来实现此方法，在C++中，我们可以用vector嵌套vector的方式来表示二维数组。
empty() 判断数组是否为空
size()返回数组中元素的数量

class Solution {
public:bool Find(int target, vector > array) {if(array.empty())  //（1）{ 	return false;}int rows = array.size(); //（2）int cols = array[0].size(); //（3）/*开始暴力遍历*/for(int i = 0;ifor(int j =0;jif(array[i][j]==target) return true;}}return false;}
};

（1）如果是空数组的话，直接返回false
（2）获取数组的行数
（3）获取数组的列数

暴力法的时间复杂度为O(mnmnmn)，其中m和n分别是数组的行数和列数。

2、二分法

暴力法虽然能解决这个问题，但是时间复杂度比较高。
但是仔细想一下，暴力查找的过程，本质就是排除的过程，如果双循环暴力查找，本质是一次排除一个，效率过低，既然是查找，就可以利用二分查找法来缩减时间复杂度。
我们可以在每一行中进行二分查找，快速定位目标值所在的行或列，进寻找目标值所在的位置，减少查找的时间复杂度。

class Solution {
public:bool Find(int target, vector > array) {if (array.empty() || array[0].empty()) {return false;}for(int i=0;iint left = 0; //（1）int right = array[i].size()-1; //（2）while(left<=right) {int mid = (left + right )/2; // （3）if(target>array[i][mid])	left = mid + 1;	//（4）else if (target

class Solution {public:bool Find(int target, vector > array) {// 判断矩阵是否为空if (array.empty() || array[0].empty()) {return false;}int i = 0; int j = array[0].size() - 1; //（1）while ( i < array.size() && j >= 0) {  if (target j--;  // （2）} else if (target > array[i][j]) {i++;  //（3）} else {return true;}}return false;}
};

class Solution {
public:bool Find(int target, vector > array) {if(array.empty()){return false;}int rows = array.size();int cols = array[0].size();for(int i = 0;ifor(int j =0;jif(array[i][j]==target)return true;}}return false;}
};

class Solution {
public:bool Find(int target, vector > array) {for(int i=0;iint low = 0;int col = array[i].size()-1;while(low<=col){int mid = (low + col )/2;if(target>array[i][mid])low = mid + 1;else if (target

class Solution {public:bool Find(int target, vector > array) {if (array.empty() || array[0].empty()) {return false;}int i = 0; int j = array[0].size() - 1; while ( i < array.size() && j >= 0) {  if (target j--;  } else if (target > array[i][j]) {i++;  } else {return true;}}return false;}
};