Search a 2D Matrix

class Solution {
  public:
  bool findInMatrix(vector<vector<int>>& grid, int value) {
    int rows = grid.size();
    if (rows == 0)
        return false;
    
    int cols = grid[0].size();
    int start = 0, end = rows * cols - 1;
    int midIndex, midValue;
    while (start <= end) {
      midIndex = (start + end) / 2;
      midValue = grid[midIndex / cols][midIndex % cols];
      if (value == midValue)
          return true;
      else {
        if (value < midValue)
            end = midIndex - 1;
        else
            start = midIndex + 1;
      }
    }
    return false;
  }
};

This summary explains how the findInMatrix function written in C++ efficiently searches for a value within a 2D matrix. The algorithm treats the matrix as if it were a 1D array, enabling the use of binary search for optimal performance.

Follow these steps to understand how the function operates:

1. Determine the number of rows in the matrix. If there are no rows, the matrix is empty and return false.
2. Calculate the number of columns based on the first row.
3. Set initial search boundaries with start set to 0 and end set to the last index in the matrix (rows * cols - 1).
4. Utilize a loop to execute until start is less than or equal to end.
5. Calculate midIndex as the average of start and end.
6. Derive midValue using midIndex to access the corresponding element in the matrix, accounting for row and column placement.
7. If the value matches midValue, return true.
8. If the value is less than midValue, adjust end to midIndex - 1 to search the lower half.
9. If the value is greater than midValue, adjust start to midIndex + 1 to search the upper half.
10. If the loop concludes without finding the value, return false.

This algorithm ensures a time-efficient search with a complexity of O(log(n)), where n is the total number of elements in the matrix. This approach significantly improves performance over a linear search especially for large matrices.

class Solution {
    public boolean findInMatrix(int[][] grid, int value) {
        int rows = grid.length;
        if (rows == 0) return false;
        int cols = grid[0].length;
    
        int start = 0, end = rows * cols - 1;
        int mid, middleElement;
        while (start <= end) {
            mid = (start + end) / 2;
            middleElement = grid[mid / cols][mid % cols];
            if (value == middleElement) return true;
            else {
                if (value < middleElement) end = mid - 1;
                else start = mid + 1;
            }
        }
        return false;
    }
}

The provided solution outlines an efficient method for searching a value in a 2D matrix using Java. The matrix is interpreted as a 1D sorted array to apply binary search, which increases the search efficiency compared to a linear scan.

In this process:

1. Initialize rows as the total number of rows in the matrix and directly return false if the matrix is empty, i.e., rows is zero.

2. Determine the number of columns containing cols.

3. Set two pointers, start and end, to cover the entire virtual 1D array representation of the matrix. start is at 0, and end is at rows * cols - 1.

4. Use a while loop to execute until start exceeds end. In each iteration, compute mid to split the dataset and middleElement to fetch the value of the midpoint using matrix indexing.

5. If value matches middleElement, return true, indicating the value is found.

6. If value is less than middleElement, adjust end to narrow the search to the left half by setting it to mid - 1.

7. Otherwise, adjust start to narrow the search to the right half by setting it to mid + 1.

8. If no match is found by the end of the loop, return false.

Adopt this binary search approach in a 2D matrix to significantly reduce the time complexity from linear to logarithmic, which is particularly advantageous when dealing with large datasets.

bool findInMatrix(int** grid, int rowCount, int* colSize, int searchValue) {
    if (rowCount == 0) return false;
    int cols = colSize[0];
    int start = 0, end = rowCount * cols - 1;
    int midIndex, midValue;
    while (start <= end) {
        midIndex = (start + end) / 2;
        midValue = grid[midIndex / cols][midIndex % cols];
        if (searchValue == midValue)
            return true;
        else {
            if (searchValue < midValue)
                end = midIndex - 1;
            else
                start = midIndex + 1;
        }
    }
    return false;
}

Solve the "Search a 2D Matrix" problem effectively using this provided C function findInMatrix. This function is designed to search for a specific integer, termed searchValue, within a matrix represented as a pointer to a pointer of integers, grid. Here are the key functionalities encapsulated in the implementation:

• Begin by handling the edge case where the matrix is empty. If rowCount equals zero, the function immediately returns false, indicating the absence of any search value.

• Calculate the total number of columns in the matrix with int cols = colSize[0];. This utilizes the first element of the colSize array for understanding matrix dimensions.

• Implement a binary search approach across the flattened matrix structure:

  • Initialize two pointers, start at 0 and end at the last index of the flattened matrix, calculated as rowCount * cols - 1.
  • Iterate while start is less than or equal to end. Compute the middle index, midIndex, and its corresponding value, midValue, using matrix row and column calculations.
  • Compare midValue with searchValue. If they match, return true indicating the searchValue is found.
  • Depending on whether searchValue is less than or greater than midValue, adjust the end or start pointers respectively to narrow down the search space.

• If the loop terminates without finding the searchValue, return false to indicate its absence in the matrix.

This function effectively leverages the sorted nature of the matrix, employing a flattened version of the binary search, which leads to an efficient solution with time complexity O(log(m*n)), where m is the number of rows and n is the number of columns in the matrix.

var findInMatrix = function (mat, val) {
    let rows = mat.length;
    if (rows == 0) return false;
    let cols = mat[0].length;
    let start = 0,
        end = rows * cols - 1;
    let mid, element;
    while (start <= end) {
        mid = Math.floor((start + end) / 2);
        element = mat[Math.floor(mid / cols)][mid % cols];
        if (val == element) return true;
        else {
            if (val < element) end = mid - 1;
            else start = mid + 1;
        }
    }
    return false;
};

In this solution, you are introduced to a method findInMatrix, implemented in JavaScript, which searches for a value in a 2D matrix. This implementation employs a binary search technique to efficiently locate the target value within the matrix.

• The function accepts two parameters: mat (the matrix), and val (the value to find).
• First, determine the number of rows in the matrix. If there are no rows (rows == 0), the function returns false, indicating the value is not found.
• Next, compute the number of columns in the matrix.
• Define starting (start) and ending (end) points for the binary search. These are set based on the total number of elements in the matrix (rows * cols - 1).
• Use a while loop to perform the binary search:
  • Compute the middle point (mid) of the current search range.
  • Convert this index into a row and column index in the 2D matrix to access the corresponding element.
  • If the target value (val) matches the element at the calculated position in the matrix, return true.
  • Adjust the start and end pointers depending on whether the target value is less or greater than the current element, narrowing the search range accordingly.
• If the search loop completes without finding the value, return false.

This efficient searching method leverages the ordered structure of a flattened 2D array, offering a time complexity of O(log(m*n)), where m is the number of matrix rows and n is the number of matrix columns. This approach is significantly faster than a linear search, especially for larger matrices.

class Solution:
    def findTarget(self, grid: List[List[int]], key: int) -> bool:
        row_count = len(grid)
        if row_count == 0:
            return False
        col_count = len(grid[0])
    
        left, right = 0, row_count * col_count - 1
        while left <= right:
            mid = (left + right) // 2
            current = grid[mid // col_count][mid % col_count]
            if key == current:
                return True
            elif key < current:
                right = mid - 1
            else:
                left = mid + 1
        return False

This Python solution efficiently searches for a target value within a 2D matrix by viewing the matrix as a flattened sorted array. Follow the steps outlined below to understand the approach taken in this implementation:

1. Calculate the total number of rows in the matrix using len(grid). Return False if the matrix is empty.
2. Determine the number of columns in the matrix with len(grid[0]).
3. Establish a range for binary search by setting left to 0 and right to (row_count * col_count - 1), essentially treating the 2D matrix as a 1D array.
4. Initiate a loop that continues as long as left is less than or equal to right.
5. Calculate the midpoint mid as (left + right) // 2.
6. Convert the mid index to the corresponding indices in the 2D matrix format, using mid // col_count for the row index and mid % col_count for the column index.
7. Compare the target key with the value at the calculated row and column index:
   • If the target equals the current matrix value, return True.
   • If the target is smaller, adjust the right index to mid - 1.
   • If the target is larger, adjust the left index to mid + 1.
8. If the loop exits without finding the target, return False.

This method uses a binary search algorithm, ensuring the solution is efficient with a time complexity of O(log(m*n)), where m is the number of rows and n the number of columns. This is ideal for large datasets, as it minimizes the number of comparisons needed to find the target value.