240. Search a 2D Matrix II

public class Solution {
    private bool BinarySearch(int[,] matrix, int target, int start, bool vertical) {
        int lo = start;
        int hi = vertical ? matrix.GetLength(1) - 1 : matrix.GetLength(0) - 1;
        while (hi >= lo) {
            int mid = (lo + hi) / 2;
            int value = vertical ? matrix[start, mid] : matrix[mid, start];
            if (value < target) {
                lo = mid + 1;
            } else if (value > target) {
                hi = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
    public bool SearchMatrix(int[,] matrix, int target) {
        if (matrix == null || matrix.Length == 0) return false;
        int shorterDim = Math.Min(matrix.GetLength(0), matrix.GetLength(1));
        for (int i = 0; i < shorterDim; i++) {
            if (BinarySearch(matrix, target, i, true) || BinarySearch(matrix, target, i, false)) {
                return true;
            }
        }
        return false;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private bool BinarySearch(int[,] matrix, int target, int start, bool vertical) {
        int lo = start;
        int hi = vertical ? matrix.GetLength(1) - 1 : matrix.GetLength(0) - 1;
        while (hi >= lo) {
            int mid = (lo + hi) / 2;
            int value = vertical ? matrix[start, mid] : matrix[mid, start];
            if (value < target) {
                lo = mid + 1;
            } else if (value > target) {
                hi = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
    public bool SearchMatrix(int[,] matrix, int target) {
        if (matrix == null || matrix.size() == 0) return false;
        int shorterDim = min(matrix.GetLength(0), matrix.GetLength(1));
        for (int i = 0; i < shorterDim; i++) {
            if (BinarySearch(matrix, target, i, true) || BinarySearch(matrix, target, i, false)) {
                return true;
            }
        }
        return false;
    }
}

class Solution {
    private boolean binarySearch(int[][] matrix, int target, int start, boolean vertical) {
        int lo = start;
        int hi = vertical ? matrix[0].length-1 : matrix.length-1;

        while (hi >= lo) {
            int mid = (lo + hi)/2;
            if (vertical) { 
                if (matrix[start][mid] < target) {
                    lo = mid + 1;
                } else if (matrix[start][mid] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            } else { 
                if (matrix[mid][start] < target) {
                    lo = mid + 1;
                } else if (matrix[mid][start] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            }
        }

        return false;
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        int shorterDim = Math.min(matrix.length, matrix[0].length);
        for (int i = 0; i < shorterDim; i++) {
            boolean verticalFound = binarySearch(matrix, target, i, true);
            boolean horizontalFound = binarySearch(matrix, target, i, false);
            if (verticalFound || horizontalFound) {
                return true;
            }
        }
        
        return false; 
    }
}

class Solution {
    binarySearch(matrix, target, start, vertical) {
        let lo = start;
        let hi = vertical ? matrix[0].length - 1 : matrix.length - 1;

        while (hi >= lo) {
            let mid = Math.floor((lo + hi) / 2);
            let value = vertical ? matrix[start][mid] : matrix[mid][start];
            if (value < target) {
                lo = mid + 1;
            } else if (value > target) {
                hi = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }

    searchMatrix(matrix, target) {
        if (!matrix || matrix.length === 0) return false;

        let shorterDim = Math.min(matrix.length, matrix[0].length);
        for (let i = 0; i < shorterDim; i++) {
            if (this.binarySearch(matrix, target, i, true) || this.binarySearch(matrix, target, i, false)) {
                return true;
            }
        }
        return false;
    }
}

class Solution:
    def binarySearch(self, matrix, target, start, vertical):
        lo = start
        hi = len(matrix[0]) - 1 if vertical else len(matrix) - 1

        while hi >= lo:
            mid = (lo + hi) // 2
            if vertical:
                if matrix[start][mid] < target:
                    lo = mid + 1
                elif matrix[start][mid] > target:
                    hi = mid - 1
                else:
                    return True
            else:
                if matrix[mid][start] < target:
                    lo = mid + 1
                elif matrix[mid][start] > target:
                    hi = mid - 1
                else:
                    return True
        return False

    def searchMatrix(self, matrix, target):
        if not matrix or not matrix[0]:
            return False

        shorterDim = min(len(matrix), len(matrix[0]))
        for i in range(shorterDim):
            if self.binarySearch(matrix, target, i, True) or self.binarySearch(matrix, target, i, False):
                return True
        return False

type Solution struct{}

func (s *Solution) binarySearch(matrix [][]int, target, start int, vertical bool) bool {
    lo := start
    hi := len(matrix[0]) - 1
    if !vertical {
        hi = len(matrix) - 1
    }

    for hi >= lo {
        mid := (lo + hi) / 2
        var value int
        if vertical {
            value = matrix[start][mid]
        } else {
            value = matrix[mid][start]
        }

        if value < target {
            lo = mid + 1
        } else if value > target {
            hi = mid - 1
        } else {
            return true
        }
    }
    return false
}

func (s *Solution) searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }

    shorterDim := len(matrix)
    if len(matrix[0]) < shorterDim {
        shorterDim = len(matrix[0])
    }

    for i := 0; i < shorter

Explanation

Algorithm

Целые числа в каждой строке отсортированы по возрастанию слева направо.

Целые числа в каждом столбце отсортированы по возрастанию сверху вниз.

Пример

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5

Output: true

👨‍💻

Алгоритм:

1️⃣

Проверка матрицы: Перед началом поиска убедитесь, что матрица не пуста и не содержит null.

2️⃣

Итерация по диагоналям: Итерируйте по диагоналям матрицы, используя инвариант отсортированности срезов строк и столбцов, начиная с текущей позиции (строка, столбец). Для каждого такого среза используйте бинарный поиск для нахождения целевого значения.

3️⃣

Бинарный поиск и завершение: Продолжайте бинарный поиск до тех пор, пока не исчерпаете все диагонали (в этом случае возвращается False) или пока не найдете целевое значение (в этом случае возвращается True). Функция бинарного поиска должна уметь работать как с рядами, так и с колонками матрицы.

😎