Search a 2D Matrix - Leetcode 74 - Binary Search (Python)

Please check my playlists for free DSA problem solutions:

My Favorite Courses:

Data Structures & Algorithms:

Python:

Web Dev / Full Stack:

Cloud Development:

Game Development:

SQL & Data Science:

Machine Learning & AI:

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[nicholassunga]

For me, this was so much easier than reading the solution that does binary search top to bottom first, then the row itself. Thank you!

[chisomedoka]

Honestly, you are very good at this. Thanks for this, very helpful

[LukeAvedon]

The best lecture on this topic. Such an elegant solution!!

[jdratlif]

I messed up at first and did a binary search for the row and then a binary search for the column, but that's not O(log(m*n)), it's O(log(m)+log(n)). It worked, but it was in the bottom 3% of runtimes, so I knew something must be wrong. As soon as I saw you use 1d indexing, it all clicked. Thanks.

[nourzakor]

when it comes to explaining binary search, you're on point, way clearer than my uni prof ever gets!

[vidhansaini]

for i in range(len(matrix)):
num = matrix[i]
left = 0
right = len(num) - 1
while left <= right:
mid = (left+right)//2
if target == num[mid]:
return True
elif target < num[mid]:
right = mid - 1
else:
left = mid + 1
continue
this code was able to pass all the test cases but have time complexity of O(m*logn) even if it does not have required time complexity this was my solution

[aar]

Thanks for the explanation. It became very clear how to write the algorithm after that explanation.

[sakshamgupta]

Thanks for the the optimization. I found an unoptimized solution, where I was simply executing binary search for each row [sub-array] which has complexity of O(nlog m)!

[prathamhebbar]

Why would you want to make sure that l <=r instead of l < r?

[Xtreme_Heat]

Thank you for the wonderful content❤❤❤❤❤❤❤❤

[ShahriyarRzayev]

If you get confused by this, m, n, t, m, i, j, here is the rewritten solution:
```
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
row_count = len(matrix)
column_count = len(matrix[0])

total_number_in_matrix = row_count * column_count
left = 0
right = total_number_in_matrix - 1

while left <= right:
middle = (left + right) // 2
row_index = middle // column_count
column_index = middle % column_count

mid_num =
if target == mid_num:
return True
elif target < mid_num:
right = middle - 1
else:
left = middle + 1

return False
```

[JourneyWithMishra]

bro please make python with DSA playlist

[kubs]

if i just flatten it and perform a binary search will my interviewer not like it?

[Xtreme_Heat]

I didn't watch the whole video because I wanted to solve it by myself 😅