# 力扣74——搜索二维矩阵

## 原题

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

```输入:
matrix = [
[1,   3,  5,  7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3

```

```输入:
matrix = [
[1,   3,  5,  7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13

```

## 解题

### 二分查找

```class Solution {

// 总行数
int row;
// 总列数
int col;

public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0 || matrix[0].length == 0) {
return false;
}

row = matrix.length;
col = matrix[0].length;
// 利用二分法查询
return binarySearchMatrix(matrix, 0, matrix.length - 1, target);
}

/**
* 查找这是矩阵的哪一行
*/
public boolean binarySearchMatrix(int[][] matrix, int left, int right, int target) {
if (left > right) {
return false;
}
if (left == right) {
int[] array = matrix[left];
if (target < array[0] || target > array[col - 1]) {
return false;
}

// 从数据中心查找
return binarySearchArray(array, 0, col - 1, target);
}

int middle = (left + right) / 2;
int[] middleArray = matrix[middle];
if (middleArray[0] > target) {
return binarySearchMatrix(matrix, left, middle - 1, target);
} else if (middleArray[col - 1] < target) {
return binarySearchMatrix(matrix, middle + 1, right, target);
} else {
return binarySearchArray(middleArray, 0, col - 1, target);
}
}

/**
* 查找这是数组中的哪个位置
*/
public boolean binarySearchArray(int[] array, int left, int right, int target) {
if (left > right) {
return false;
}
if (left == right) {
return array[left] == target;
}

int middle = (left + right) / 2;
if (array[middle] > target) {
return binarySearchArray(array, left, middle - 1, target);
} else if (array[middle] == target) {
return true;
} else {
return binarySearchArray(array, middle + 1, right, target);
}
}
}
```

### 优化

```class Solution {

public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0 || matrix[0].length == 0) {
return false;
}

int col = matrix[0].length;
// 将二维数组拉成一维数组，利用二分法解决
int left = 0;
int right = matrix.length * col - 1;
while (left <= right) {
// 计算中间数的下标和值
int middleIndex = (left + right) / 2;
int middleVal = matrix[middleIndex / col][middleIndex % col];
if (middleVal == target) {
return true;
}

if (middleVal < target) {
left = middleIndex + 1;
} else {
right = middleIndex - 1;
}
}

return false;
}
}
```

## 总结

https://death00.github.io/

0 条评论

• ### Java面试-动态规划与组合数

最近在刷力扣上的题目，刷到了65不同路径，当初上大学的时候，曾在hihocoder上刷到过这道题目，但是现在已经几乎全忘光了，大概的知识点是动态规划，如今就让我...

• ### 力扣240——搜索二维矩阵

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

• ### 力扣221——最大正方形

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

• ### 直接插入排序 希尔排序

【1 2 3 4  7 8 9】 6 插入3， 3和 9 交换，3和8交换， 3和7交换， 3和4交换

• ### 【leetcode】3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is cl...

• ### hdu------(1525)Euclid's Game(博弈决策树)

Euclid's Game Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3276...

• ### LintCode 子树题目分析代码

有两个不同大小的二进制树： T1有上百万的节点； T2有好几百的节点。请设计一种算法，判定 T2是否为 T1的子树。

• ### java原生实现屏幕设备遍历和屏幕采集（捕获）等功能

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