74. 搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
题目来源：力扣（LeetCode）
二分法思路
能否写出：能写出。
时间：20多分钟
思路：
大体思路与二分法查找思路一样，从小白开始刷算法 二分法篇 leetcode.704
需要注意的是在二维数组中，索引位置的转换涉及到行和列的关系。通常情况下，二维数组的索引由两个值表示，分别是行索引和列索引。
如果给定一个二维数组 matrix，其中 matrix[i][j] 表示第 i 行第 j 列的元素，那么可以使用以下公式进行索引位置的转换：
- 将二维索引转换为一维索引：
index = i * numColumns + j
其中，i是行索引，j是列索引，numColumns是二维数组的列数。
这个公式将二维索引转换为一维索引，可以用于将二维数组表示的矩阵转换为一维数组进行处理。
将一维索引转换为二维索引：
i = index / numColumns
j = index % numColumns
其中，index 是一维索引，numColumns 是二维数组的列数。
- 这个公式将一维索引转换为对应的行索引和列索引，可以用于从一维数组中还原出二维数组的索引位置。
通过以上的索引转换公式，可以在处理二维数组时方便地进行索引位置的转换。
转换
// 仅是我的思路代码，leetcode上大神更厉害 class Solution { public boolean searchMatrix(int[][] matrix, int target) { int row = matrix[0].length; int col = matrix.length; int start = 0; int end = row * col -1; while (start <= end) { int mid = start+(end - start)/2; //通过计算得出二维数组的位置 int e = matrix[mid / row][mid % row]; if(e==target){ return true; } if(e>target){ end = mid-1; }else { start= mid+1; } } return false; } }
时间复杂度： O(log n)
空间复杂度：O(1)
