题目
74. 搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
示例 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
提示： - m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -104 <= matrix[i][j], target <= 104
我的代码（Python）
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
if matrix[0][0] > target or matrix[m - 1][n - 1] < target:
return False
if matrix[m - 1][n - 1] == target or matrix[m - 1][0] == target:
return True
# row
rs, re = 0, m - 1
while rs < re:
# print(f'rs: {rs}, re: {re}')
# if matrix[rs][0] == target or matrix[re][0] == target:
# return True
# if matrix[rs][0] > target:
# return False
if matrix[re][0] < target:
rs = re
break
if re - rs == 1:
break
rmid = (rs + re) // 2
if matrix[rmid][0] == target:
return True
if matrix[rmid][0] < target:
rs = rmid
if matrix[rmid][0] > target:
re = rmid
r = rs
# column
cs, ce = 0, n - 1
if matrix[r][cs] == target or matrix[r][ce] == target:
return True
while cs < ce:
# if matrix[r][cs] == target or matrix[r][ce] == target:
# return True
if matrix[r][cs] > target or matrix[r][ce] < target:
return False
if ce - cs == 1:
break
cmid = (cs + ce) // 2
if matrix[r][cmid] == target:
return True
if matrix[r][cmid] < target:
cs = cmid
if matrix[r][cmid] > target:
ce = cmid
return matrix[r][cs] == target点评
实际上就是一个递增序列，只是放成矩阵形式。
比起240. 搜索二维矩阵 II不是一个思路，简化很多。
我的解法
我的做法是先二分查找行，确定在哪一行再二分查找列。
也可以用整个数组的长度来做二分查找，然后每个索引计算它实际的行列数。
两者时间复杂度应该是一样的。
官方两种解法就是这个思路。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog
[每日一题][找工作第58天][2025-11-19] Leetcode 35. 搜索插入位置
题目
35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
提示:
- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
- nums 为 无重复元素 的 升序 排列数组
- -104 <= target <= 104
我的代码（Python）
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
s, e = 0, len(nums) - 1
if nums[s] >= target:
return s
if nums[e] == target:
return e
if nums[e] < target:
return e + 1
while s < e:
if s == e - 1:
return e
m = (s + e) // 2
if nums[m] == target:
return m
elif nums[m] < target:
s = m
else:
e = m
return s点评
简单粗暴的二分查找，上下限索引的正确迭代和特殊情况的处理是关键点。
我比官方解法多做了一些特殊情况的代码处理，不过相对的效率会高一些。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog