面试题04. 二维数组中的查找

题目描述

有序二维数组的查找

做题链接：面试题04. 二维数组中的查找

同 搜索二维矩阵 II

解题思路

方法一： 左下/右上元素移动法【Best Answer】

根据左下、右上角的特点是，排除式查找。

时间复杂度 $O(行高+列高)$ 空间复杂度 $O(1)$

方法二：双折半查找

时间复杂度：$O(logM + logN)$ 复杂度最坏情况为 $O(M * logN)$

参考：https://blog.nowcoder.net/n/d332492753844d18aa4edc484e3c1318

二维数组分为上下左右四个边界top，bottom，left，right：

- 根据上边界折半查找——确定 right 范围
- 根据下边界折半查找——确定 left 范围
- 根据左边界折半查找——确定 top 范围
- 根据右边界折半查找——确定 bottom 范围

最直接的方法，代码量大，考察基本功

代码

方法一

class Solution:
      def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
          if not matrix: return False
          # 以右上角为例
          i, j = 0, len(matrix[0]) - 1
          while i < len(matrix) and j >= 0:
              if matrix[i][j] == target: return True
              elif matrix[i][j] < target: i += 1 # 比目标值小，向下一行查找
              else: j -= 1 # 比目标值大，向上一行查找
          return False

方法二

  class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        left = 0
        right = len(array[0]) - 1 
        top = 0
        bottom = len(array) - 1 
        
        while (left < right or top < bottom):
             # 对上边界进行折半，可以缩小右边界
             l = left
             r = right
             while (l <= r):
                  mid = (l+r) // 2
                  if array[top][mid] == target:
                       return True
                  elif array[top][mid] > target:
                       r = mid - 1
                  else:
                       l = mid + 1
             if (mid < right):
                  right = mid
             top += 1

             # 对下边界进行折半，可以缩小左边界
             l = left
             r = right
             while (l <= r):
                  mid = (l + r) // 2 
                  if array[bottom][mid] == target:
                       return True
                  elif array[bottom][mid] > target:
                       r = mid - 1 
                  else: 
                       l = mid + 1 
             if (mid > left):
                 left = mid 
             bottom -= 1

             # 对左边界进行折半，可以缩小下边界
             t = top
             b = bottom
             while (t <= b):
                 mid = (t + b) // 2 
                 if array[mid][left] == target:
                      return True
                 elif array[mid][left] > target:
                      b = mid - 1 
                 else: 
                      t = mid + 1 
             if (t < mid):
                 t = mid
             left += 1

             # 对右边界进行折半，可以缩小上边界
             t = top
             b = bottom
             while (t <= b):
                mid = (t + b) // 2 
                if array[mid][right] == target:
                     return True
                elif array[mid][right] > target:
                     b = mid - 1 
                else:
                     t = mid + 1 
             if (b > mid):
                 b = mid 
             right -= 1 

        return False