Skip to content

Latest commit

 

History

History
11 lines (7 loc) · 946 Bytes

README.md

File metadata and controls

11 lines (7 loc) · 946 Bytes

如果是一维矩阵,直接使用二分查找,二分查找每次可以将查找范围缩小到一个子数组中,因此考虑利用这种思想处理

如果使用矩阵中间的元素进行判断,那么当中间元素小于target时,target可能出现在上面,也可能出现在左边;当中间元素大于target时,target可能出现在右边或下面;那么就都会出现2种情况,一种情况需要修改row,不好处理

可以从右上角或者左下角进行查找,以右上角为例:

  • 如果元素大于target,则删除一行,因为该元素左侧的元素都比该元素小,从而都小于target
  • 如果元素小于target,则删除一列,因为该元素下面的元素都比该元素大,从而都大于target
  • 如果元素等于target,则返回true

以这种方式,每次只需递增row或减小col从而删除一行或一列,最终如果出现越界,说明元素不存在矩阵中