从小白开始刷算法 二分法篇 leetcode.74

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 列的元素，那么可以使用以下公式进行索引位置的转换：

1. 将二维索引转换为一维索引：
   index = i * numColumns + j
   其中，i 是行索引，j 是列索引，numColumns 是二维数组的列数。
   这个公式将二维索引转换为一维索引，可以用于将二维数组表示的矩阵转换为一维数组进行处理。
   

将一维索引转换为二维索引：

i = index / numColumns

j = index % numColumns

其中，index 是一维索引，numColumns 是二维数组的列数。

1. 这个公式将一维索引转换为对应的行索引和列索引，可以用于从一维数组中还原出二维数组的索引位置。
   

通过以上的索引转换公式，可以在处理二维数组时方便地进行索引位置的转换。

转换

// 仅是我的思路代码，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)