Search A 2D Matrix

                                            
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        
        int left = 0;
        int right = m * n - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midElement = matrix[mid / n][mid % n];
            
            if (midElement == target) {
                return true;
            } else if (midElement < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;
    }
};

                                            
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        
        int left = 0;
        int right = rows * cols - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midElement = matrix[mid / cols][mid % cols];
            
            if (midElement == target) {
                return true;
            } else if (midElement < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;
    }
}

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

                                            
bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
    int m = matrixSize;
    int n = *matrixColSize;
    
    int low = 0;
    int high = m * n - 1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int midElement = matrix[mid / n][mid % n];
        
        if (midElement == target) {
            return true;
        } else if (midElement < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    return false;
}

                                            
public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        int m = matrix.Length;
        int n = matrix[0].Length;

        int left = 0;
        int right = m * n - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midElement = matrix[mid / n][mid % n];
            
            if (midElement == target) {
                return true;
            } else if (midElement < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;
    }
}

                                            
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
const searchMatrix = (matrix, target) => {
    if (matrix.length === 0) {
        return false;
    }
    
    const rows = matrix.length;
    const cols = matrix[0].length;
    let left = 0;
    let right = rows * cols - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const midVal = matrix[Math.floor(mid / cols)][mid % cols];
        
        if (midVal === target) {
            return true;
        } else if (midVal < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return false;
};

                                            
function searchMatrix(matrix: number[][], target: number): boolean {
    let rows = matrix.length;
    let cols = matrix[0].length;
    
    let left = 0;
    let right = rows * cols - 1;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let midVal = matrix[Math.floor(mid / cols)][mid % cols];
        
        if (midVal === target) {
            return true;
        } else if (midVal < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return false;
}

                                            
class Solution {
    /**
     * @param Integer[][] $matrix
     */
    function searchMatrix($matrix, $target) {
        $m = count($matrix);
        $n = count($matrix[0]);
        
        $left = 0;
        $right = $m * $n - 1;
        
        while ($left <= $right) {
            $mid = $left + intval(($right - $left) / 2);
            $row = intval($mid / $n);
            $col = $mid % $n;
            
            if ($matrix[$row][$col] == $target) {
                return true;
            } else if ($matrix[$row][$col] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }
        
        return false;
    }
}

                                            
class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        guard !matrix.isEmpty, !matrix[0].isEmpty else {
            return false
        }
        
        let row = matrix.count
        let col = matrix[0].count
        var left = 0
        var right = row * col - 1
        
        while left <= right {
            let mid = left + (right - left) / 2
            let midElement = matrix[mid / col][mid % col]
            
            if midElement == target {
                return true
            } else if midElement < target {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return false
    }
}

                                            
class Solution {
    fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
        if (matrix.isEmpty() || matrix[0].isEmpty()) {
            return false
        }
        
        val rows = matrix.size
        val cols = matrix[0].size
        
        var left = 0
        var right = rows * cols - 1
        
        while (left <= right) {
            val mid = left + (right - left) / 2
            val midElement = matrix[mid / cols][mid % cols]
            
            if (midElement == target) {
                return true
            } else if (midElement < target) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return false
    }
}

                                            
class Solution {
  bool searchMatrix(List<List<int>> matrix, int target) {
    int m = matrix.length;
    int n = matrix[0].length;
    
    int left = 0;
    int right = m * n - 1;
    
    while (left <= right) {
      int mid = left + ((right - left) ~/ 2);
      int midElement = matrix[mid ~/ n][mid % n];
      
      if (midElement == target) {
        return true;
      } else if (midElement < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    
    return false;
  }
}

                                            
func searchMatrix(matrix [][]int, target int) bool {
    m := len(matrix)
    if m == 0 {
        return false
    }
    n := len(matrix[0])
    low, high := 0, m*n-1

    for low <= high {
        mid := low + (high-low)/2
        midVal := matrix[mid/n][mid%n]

        if midVal == target {
            return true
        } else if midVal < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }

    return false
}

                                            
# @param {Integer[][]} matrix
# @param {Integer} target
# @return {Boolean}
def search_matrix(matrix, target)
    m = matrix.length
    n = matrix[0].length
    left = 0
    right = m * n - 1
    
    while left <= right
        mid = left + (right - left) / 2
        mid_val = matrix[mid / n][mid % n]
        
        if mid_val == target
            return true
        elsif mid_val < target
            left = mid + 1
        else
            right = mid - 1
        end
    end
    
    return false
end

                                            
object Solution {
    def searchMatrix(matrix: Array[Array[Int]], target: Int): Boolean = {
        if (matrix.isEmpty || matrix(0).isEmpty) {
            return false
        }
        
        val m = matrix.length
        val n = matrix(0).length
        
        var left = 0
        var right = m * n - 1
        
        while (left <= right) {
            val mid = left + (right - left) / 2
            val midElement = matrix(mid / n)(mid % n)
            
            if (midElement == target) {
                return true
            } else if (midElement < target) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        false
    }
}

                                            
impl Solution {
    pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
        if matrix.is_empty() || matrix[0].is_empty() {
            return false;
        }
        
        let rows = matrix.len();
        let cols = matrix[0].len();
        
        let mut left = 0;
        let mut right = (rows * cols) as i32 - 1;
        
        while left <= right {
            let mid = left + (right - left) / 2;
            let mid_element = matrix[mid as usize / cols][mid as usize % cols];
            
            if mid_element == target {
                return true;
            } else if mid_element < target {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        false
    }
}

                                            
-spec search_matrix(Matrix :: [[integer()]], Target 
:: integer()) -> boolean().
search_matrix(Matrix, Target) ->
    Rows = lists:flatten(Matrix),
    lists:member(Target, Rows).

To solve this coding challenge, we need to efficiently search for a target value in a 2D matrix that has distinct, sorted rows and columns. Since rows are sorted in non-decreasing order and the first integer of each row is greater than the last integer of the previous row, the matrix can be visualized as a single flattened, sorted array. This allows us to use binary search to achieve an O(log(m*n)) time complexity.

# Explanation:

Matrix and Binary Search Setup :

Each element in the matrix can be uniquely indexed using two coordinates, namely row and column indices.
Since the matrix elements are sorted in a row-major order, it's feasible to map a 2D index to a 1D index, which is conducive to applying binary search.

Defining Matrix Dimensions :

We determine the number of rows
m

and columns
n

from the matrix.

Binary Search Implementation :

Initialize two pointers
left

and
right

to the beginning and end of the hypothetical 1D array that the 2D matrix represents.
Calculate the middle index
mid

and map it back to its 2D coordinates (row and column).
Compare the middle element with the target. If it matches, return
True

.
Adjust the search range based on whether the middle element is less than or greater than the target.
If pointers cross without finding the element, return
False

.

Here’s the pseudocode that encapsulates the above steps:

# Pseudocode with Comments:

                                            
# Given a matrix and a target value
# Initialize matrix dimensions
rows = number of rows in matrix
columns = number of columns in matrix

# Initialize search boundary pointers
left = 0
right = (rows * columns) - 1

# Conduct binary search
while left <= right:
# Calculate the middle index
mid = left + (right - left) // 2

# Map mid index back to 2D coordinates
row_index = mid // columns
column_index = mid % columns
mid_element = matrix[row_index][column_index]

# Compare the middle element with the target value
if mid_element == target:
return True # Target found
elif mid_element < target:
left = mid + 1 # Adjust the search to the right half
else:
right = mid - 1 # Adjust the search to the left half

# Target is not found in the matrix
return False

# Detailed Steps in Pseudocode:

Matrix Initialization :

rows = len(matrix)

calculates the number of rows in the matrix.
columns = len(matrix[0])

calculates the number of columns in the matrix.

Binary Search Initialization :

left = 0

sets the left boundary to the start of the 1D representation of the matrix.
right = (rows * columns) - 1

sets the right boundary to the end of the 1D representation.

Binary Search Loop :

Mid Calculation :
mid = left + (right - left) // 2

calculates the middle index.
Mapping to 2D Coordinates :

row_index = mid // columns

maps the middle index to the corresponding row.
column_index = mid % columns

maps the middle index to the corresponding column.
mid_element = matrix[row_index][column_index]

retrieves the middle element from the matrix.

Comparison :

If
mid_element == target

: Return
True

(target found).
If
mid_element < target

: Move the
left

pointer to
mid + 1

to search the right half.
If
mid_element > target

: Move the
right

pointer to
mid - 1

to search the left half.

End Condition :

If the loop exits without finding the target, return
False

.

This method effectively leverages binary search with adjustments for matrix-based indexing, ensuring an efficient solution with O(log(m*n)) time complexity.