leetcode 第74题搜索二维矩阵

    技术2026-02-20  18

    二分法查找的话,总是会有一些细节没有看出来。

    编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

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

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/search-a-2d-matrix 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    class Solution { public boolean searchMatrix(int[][] matrix, int target) { if(matrix.length == 0 || matrix[0].length == 0)//必须两个都判断 return false ; int m0 = 0 ; int n0 = 0 ; int m = matrix.length-1 ;//长度减一 int n = matrix[0].length-1; while(m0 <= m){ int midm = m0 + ( m - m0 ) / 2 ; if(matrix[midm][0] == target){ return true ; } if(matrix[midm][0] < target && matrix[midm][n] >= target){ while(n0 <= n){ int midn = (n0 + n)/2 ; if(matrix[midm][midn] == target){ return true ; } if(matrix[midm][midn] < target){ n0 = midn + 1 ; }else{ n = midn - 1 ; } } break ; } else if(matrix[midm][0] < target && matrix[midm][n] < target){ m0 = midm + 1 ; }else{ m = midm - 1 ; } } return false ; } }

    两次二分法查找, 时间复杂度:O(logmn)

    Processed: 0.026, SQL: 9