CareerCup

There are surprisingly 4 solutions to this problem! We can start with the brute force and improve from O(n^2) -> O(nlogn) -> O(n) -> O(lgn). I have outlined the 4 solutions below with explanations.
PS:- I would appreciate if you can plz upvote :P, I put in some effort to clearly explain the solution. :P

Python solution:

# Brute Force - Look at each element one by one
# O(n^2) solution
def searchVersion1(matrix, target):
  for i, row in enumerate(matrix):
    for j, sq in enumerate(row):
      if sq == target:
        return True
  return False

# Since each row is sorted, perform binary search
# Since there are n rows, the runtime is O(n*lgn)
def searchVersion2(matrix, target):
  def binarySearchHelper(row, target, low, high):
    while low <= high:
      mid = (low + high) // 2
      if row[mid] == target:
        return True
      elif row[mid] < target:
        low = mid + 1
      elif row[mid] > target:
        high = mid - 1
    return False

  for i, row in enumerate(matrix):
    if binarySearchHelper(row, target, 0, len(row)-1):
      return True
  return False

# O(n) solution
# We can start from top-right corner of the matrix
# and move up to bottom right. If current element < target, move down
# else if element > target, move left. If we go out of bounds, we can
# return False since the element is not found.
def searchVersion3(matrix, target):
  x, y = 0, len(matrix[0])-1

  while 0 <= x < len(matrix) and 0 <= y < len(matrix[0]):
    currentElement = matrix[x][y]
    if currentElement == target:
      return True
    elif currentElement < target:
      x += 1 # Move down
    elif currentElement > target:
      y -= 1 # Move left
  return False

# O(lgn) solution
# Treat the 2-d matrix as a 1-d sorted array
# and just map the indices using math while applying binary search.
def searchVersion4(matrix, target):
  rows, cols = len(matrix), len(matrix[0])
  low, high = 0, rows * cols - 1

  while low <= high:
    mid = (low + high) // 2
    curRow = mid // cols
    curCol = mid % cols
    currentElement = matrix[curRow][curCol]
    if currentElement == target:
      return True
    elif currentElement < target:
      low = mid + 1
    else:
      high = mid - 1
  return False


matrix =  \
[
  [1 , 3, 5, 7, 9] ,
  [11,13,15,16,20],
  [21,22,23,24,25],
  [30,32,35,40,45],
]

print(searchVersion1(matrix, 23)) # True
print(searchVersion1(matrix, 28)) # False
print(searchVersion1(matrix, 5)) # True
print(searchVersion1(matrix, 10))# False
print('#' * 20)
print(searchVersion2(matrix, 23))# True
print(searchVersion2(matrix, 28))# False
print(searchVersion2(matrix, 5))# True
print(searchVersion2(matrix, 10))# False
print('#' * 20)
print(searchVersion3(matrix, 23))# True
print(searchVersion3(matrix, 28))# False
print(searchVersion3(matrix, 5))# True
print(searchVersion3(matrix, 10))# False
print('#' * 20)
print(searchVersion4(matrix, 23))# True
print(searchVersion4(matrix, 28))# False
print(searchVersion4(matrix, 5))# True
print(searchVersion4(matrix, 10))# False

Binary search to find the row and binary search to find the element in the row, log(n) + log(n). Complexity should be log(n).

Also, you can do a single binary search, if you can mange the index conversion from two dimensional to single dimensional. As in (row, column) (2,3) means index 2n+3. So you can run in binary search on from 1 and n*n.