Start learning free

LESSON 326 OF 536 · BINARY SEARCH

Search a 2D Matrix in Python: O(log(m * n)) Binary Search

Practice O(log(m · n)) Read the full explanation

You are given a matrix of integers matrix with m rows and n columns, and an integer target. The matrix has two properties:

  • Each row is sorted in non-decreasing order.
  • The first value of each row is greater than the last value of the row before it.

Return True if target is in matrix, or False otherwise.

The matrix is a list of rows, and each row is a list of integers. Rows are numbered from 0, top to bottom, and columns from 0, left to right.

 

Example 1:

Input: matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
], target = 3
Output: True
Explanation: 3 is in row 0, column 1.

Example 2:

Input: matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
], target = 13
Output: False
Explanation: 13 would sit between 11 and 16 in row 1, but it isn't there.

Example 3:

Input: matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
], target = 30
Output: True
Explanation: Read row by row, the 12 values form one sorted list:
1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60.
30 is at position 9 of that list (counting from 0), which is row 2, column 1.

 

Constraints:

  • 1 <= m, n <= 1000
  • -109 <= matrix[i][j], target <= 109
  • Every row has n values, sorted in non-decreasing order, and each row starts with a value greater than the last value of the row before it.

Note:

Your algorithm should run in O(log(m · n)) time and use O(1) extra space. Checking every cell would take O(m · n).

STEP 1 OF 9
    Ctrl + Enter to check

    PYTHON · BINARY SEARCH

    Search A 2d Matrix in Python, explained

    Problem overview

    The method searchMatrix receives matrix, a list of rows where each row is a list of integers, and an integer target. It returns True if target appears anywhere in the matrix and False otherwise.

    The matrix has two properties. Every row is sorted in non-decreasing order, and the first value of each row is greater than the last value of the row before it. Together they mean something stronger than "each row is sorted": if you read the rows one after another, the whole matrix is a single sorted list.

    Take matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]. Read row by row, it is 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60. With target = 3 the answer is True, and with target = 13 it is False: 13 would sit between 11 and 16, but it isn't there. With target = 30 the answer is True.

    Approach: binary search over positions, not cells

    Checking every cell costs O(m * n). The statement asks for O(log(m * n)) time and O(1) extra space, which is what binary search on a sorted sequence of m * n values gives.

    The obstacle is that the data is a list of lists, not one flat list. You could build the flat list first, but that takes O(m * n) time and space and defeats the purpose. Instead, imagine the flat list and compute where each of its positions lives in the matrix. Position p counts from 0 across the rows. Each row holds n values, so the positions before p fill p // n whole rows and then p % n cells of the next one. That makes position p the cell at row p // n, column p % n. With 4 columns, position 9 is row 2, column 1, and that cell holds 30.

    The search is then ordinary binary search on the positions 0 to m * n - 1. At each step it compares the value at the middle position with the target, and discards the half that can't contain it.

    For target = 30 the search goes like this:

    left=0 right=11 middle=5 cell=(1,1) value=11
left=6 right=11 middle=8 cell=(2,0) value=23
left=9 right=11 middle=10 cell=(2,2) value=34
left=9 right=9 middle=9 cell=(2,1) value=30

    The values 11, 23 and 34 are all compared against 30, and each comparison moves a boundary. The fourth middle is position 9, which holds 30, so the method returns True. For target = 13 the range shrinks to positions 6 and 7 and then empties, so the method returns False.

    Step by step

    1. Read the dimensions. m is the number of rows, len(matrix). n is the number of columns, the length of the first row, which is enough because every row has the same length. One tuple assignment sets both.
    2. Set the search range as left and right, again in one assignment: 0 and m * n - 1. Both ends are inclusive, so right is the last position itself.
    3. Loop while left <= right. With <=, a range holding a single position still gets checked.
    4. Take the middle position as left + (right - left) // 2. Floor division keeps it an integer.
    5. Convert the position to a cell. The row is middle // n, the column is middle % n, and value holds what is there. This is the key idea of the lesson.
    6. Return True on a match.
    7. If value is smaller than the target, the target can only be at a later position, so left becomes middle + 1.
    8. Otherwise the value is too big, so right becomes middle - 1.
    9. After the loop, no position is left to check, so return False.

    The solution in Python

    class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1
        while left <= right:
            middle = left + (right - left) // 2
            value = matrix[middle // n][middle % n]
            if value == target:
                return True
            elif value < target:
                left = middle + 1
            else:
                right = middle - 1
        return False

    Python details worth a closer look:

    • Tuple assignment. m, n = len(matrix), len(matrix[0]) builds a tuple on the right and unpacks it into two names. Both right-hand expressions are evaluated before either name is assigned.
    • Floor division. // divides and rounds down to an integer, while / always returns a float. Using / would make middle a float, and a list can't be indexed with one: matrix[1.0] raises a TypeError.
    • The overflow-safe midpoint. left + (right - left) // 2 is the habit from languages with fixed-size integers. Python integers never overflow, so (left + right) // 2 gives the same result here.
    • Two index operations. matrix[middle // n] picks a row, which is a list, and [middle % n] picks a value from it. No list of all the values is ever built, which is why the extra space stays O(1).
    • Negative indices. Python accepts matrix[-1] and counts from the end, so a bug that produces a negative position wouldn't raise an error and would silently read the wrong cell. Here the positions always stay between left and right, so they are never negative.

    Complexity

    Time: O(log(m * n)). Each pass of the loop halves the range of positions still to check, starting from m * n. A matrix with a million cells needs about 20 passes. Each pass does a constant amount of work: one division, one remainder and two index operations.

    Space: O(1). The method keeps a handful of integers, whatever the size of the matrix.

    Two other ideas also work, and both are slower or longer. Searching each row with binary search costs O(m * log n). Binary searching the first column to pick a row, and then binary searching that row, costs O(log m + log n), which is the same as O(log(m * n)) but takes two loops.

    Edge cases and common mistakes

    • A single cell. [[5]] has one position, 0. With target 5 the method returns True and with target 4 it returns False. The constraints guarantee at least one row and one column, so len(matrix[0]) is safe.
    • A single column. [[1], [3], [5]] has n = 1, so every position is its own row: middle // 1 is the row and middle % 1 is always 0. Searching for 3 returns True.
    • Targets outside the range. A target below the first value or above the last one is ruled out by the loop. In the example matrix, 0 and 61 both give False.
    • The first and last values. 1 and 60 are found like any other value, because both ends of the range are inclusive.
    • Using left < right. When one position remains, the loop stops without looking at it, so a target at that position is reported as missing.
    • Setting left = middle or right = middle. The value at middle was already checked. Keeping it in the range can make the loop run forever.
    • Mixing up the row and the column. The row is middle // n and the column is middle % n, where n is the number of columns. Dividing by m only works for a square matrix, and it is wrong for the 3-by-4 example.

    Testing

    With matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]:

    • target = 3 gives True.
    • target = 13 gives False.
    • target = 30 gives True.
    • target = 60 gives True.
    • target = 0 gives False.
    • target = 61 gives False.

    With matrix = [[1], [3], [5]], target = 3 gives True. With matrix = [[5]], target = 5 gives True and target = 4 gives False.

    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free