二维数组binary search
时间: 2023-11-11 18:02:18 浏览: 48
二维数组二分查找的基本思路是将二维数组展开成一维数组,然后在一维数组上进行二分查找。
具体实现可以按照行优先或列优先的顺序将二维数组展开为一维数组。在行优先的情况下,将二维数组的行按照顺序拼接成一个一维数组;在列优先的情况下,将二维数组的列按照顺序拼接成一个一维数组。这里以行优先的方式为例进行讲解。
假设二维数组为 $matrix$,行数为 $m$,列数为 $n$,要查找的值为 $target$。将二维数组展开成一维数组 $nums$,则有 $nums[i*n+j]=matrix[i][j]$。可以使用二分查找算法在 $nums$ 数组中查找 $target$。
具体的二分查找实现可以参考以下代码:
```python
def searchMatrix(matrix, target):
if not matrix or not matrix[0]:
return False
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1
while left <= right:
mid = (left + right) // 2
if matrix[mid // n][mid % n] == target:
return True
elif matrix[mid // n][mid % n] < target:
left = mid + 1
else:
right = mid - 1
return False
```
这个算法的时间复杂度是 $O(\log(mn))$,空间复杂度是 $O(1)$。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)