74. Search a 2D Matrix

📝 Problem Details

• Title: 74. Search a 2D Matrix
• Link: https://leetcode.com/problems/search-a-2d-matrix/
• Difficulty: Medium
• Tags/Categories: Arrays Matrix Binary-Search

💭What Were My Initial Thoughts?

- brute force approach would be just iterating through every element in the matrix and checking if it equals our target value
	- this would be O(n*m) time, which is not acceptable for the constraint of it being O(log(m*n))

- the input matrix is sorted (this helps)
- a logarithmic solution for searching for an element would be some form of binary search

🤔What Did I Struggle With?

- nailed this question in the mock, just ran out of time by like a minute due to spending too much time of the first question 

💡 Explanation of Solution

We can leverage binary search twice:

1. **Binary Search on Rows:**
    - Treat the matrix as a list of rows.
    - Use binary search to identify the row that could potentially contain the target.
    - This works because the first and last elements of each row provide a range.

1. **Binary Search on Columns (within the selected row):**
    - Once the row is identified, perform binary search within that row to find the target.
    - This works because each row is sorted.

⌛ Complexity Analysis

Time Complexity: O(log (n*m))
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int lowRow = 0;
        int highRow = matrix.size() - 1;
        
        while( lowRow < highRow){
            int mid = lowRow + (highRow - lowRow) / 2;
 
            if(matrix[mid][0] == target) {
	            return true;
			}
			
            if(matrix[mid][0] < target && target < matrix[mid + 1][0]){
                lowRow = mid;
                break;
            }
 
            if(matrix[mid][0] < target){
                lowRow = mid + 1;
            } else {
                highRow = mid - 1;
            }
        }
 
        int lowCol = 0;
        int highCol = matrix[0].size() - 1;
 
        while(lowCol <= highCol){
            int mid = lowCol + (highCol - lowCol) / 2;
            
            if(matrix[lowRow][mid] == target){
                return true;
            }
 
            if(matrix[lowRow][mid] < target){
                lowCol = mid + 1;
            } else {
                highCol = mid - 1;
            }
        }
        return false;
    }
};