Advertisement
imashutosh51

Search in a matrix whose elements are sorted in insertion order

Aug 11th, 2022 (edited)
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.71 KB | None | 0 0
  1. /*
  2. https://leetcode.com/problems/search-a-2d-matrix/
  3. Logic:binary search
  4. We are just considering matrix as 1d arrray and whenever we need to find the element at
  5. nth position,we find using find_ele function.
  6. */
  7. def bs(matrix,row,col,i,j,target):
  8.     if i>j:
  9.         return False
  10.     mid=(i+j)//2
  11.     if matrix[mid//col][mid%col]==target:
  12.         return True
  13.     if matrix[mid//col][mid%col]<target:
  14.         return bs(matrix,row,col,mid+1,j,target)
  15.     else:
  16.         return bs(matrix,row,col,i,mid-1,target)
  17.  
  18. class Solution:
  19.     def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
  20.         row=len(matrix)
  21.         col=len(matrix[0])
  22.         return bs(matrix,row,col,0,row*col-1,target)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement