Day 22: Search a 2D Matrix: Binary Search - leetcode - Python3

 You are given an m x n integer matrix matrix with the following two properties:

• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

 

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

SOLUTION

class Solution:

    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:

       

        m, n = len(matrix), len(matrix[0])

        firstRow, lastRow = 0, m-1

        while firstRow <= lastRow:#log m

            mid = (firstRow + lastRow ) // 2

            if target > matrix[mid][-1]:

                firstRow = mid + 1

            elif target < matrix[mid][0]:

                lastRow = mid - 1

            else:

                break

        if not (firstRow <= lastRow):

            return False

        row = (firstRow + lastRow)//2    

        l, r = 0, n-1

       

        while l <= r:

            m = (l+r)//2

            if target > matrix[row][m]:

                l = m + 1

            elif target < matrix[row][m]:

                r = m - 1

            else:

                return True

        return False

Time Complexity: O(log m*n)

Space Complexity:O(1)

How it works:

1. Obtain the dimensions of the matrix: m represents the number of rows, and n represents the number of columns.

2. Initialize firstRow and lastRow to track the boundaries of the search range in the matrix. Set firstRow as 0 (the first row) and lastRow as m-1 (the last row).

3. Perform a binary search to find the row where the target might be present:

   • While firstRow is less than or equal to lastRow, calculate the middle row as mid using integer division.
   • If the target is greater than the last element in the mid row, update firstRow to mid + 1 to search in the lower half of the remaining matrix.
   • If the target is less than the first element in the mid row, update lastRow to mid - 1 to search in the upper half of the remaining matrix.
   • If neither condition is met, it means the target might be in the mid row, so break the loop.

4. Check if the search range is valid:

   • If firstRow is greater than lastRow, it means the target is not present in the matrix, so return False.

5. Calculate the actual row index, row, where the target might be present by taking the average of firstRow and lastRow.

6. Initialize l and r to track the boundaries of the search range within the chosen row. Set l as 0 (the first column) and r as n-1 (the last column).

7. Perform a binary search within the chosen row to find the target value:

   • While l is less than or equal to r, calculate the middle column as m using integer division.
   • If the target is greater than the value at matrix[row][m], update l to m + 1 to search in the right half of the remaining row.
   • If the target is less than the value at matrix[row][m], update r to m - 1 to search in the left half of the remaining row.
   • If neither condition is met, it means the target is found at matrix[row][m], so return True.

8. If the target is not found within the chosen row, return False.

The code performs two binary searches: one to find the row where the target might be present and another to search for the target within that row. If the target is found, the code returns True; otherwise, it returns False.