# 240. Search a 2D Matrix II

題目：<https://leetcode.com/problems/search-a-2d-matrix-ii/>

解法：先取其中一行，進行 binary search，如果沒找到再依據最接近的位置，可以排除左上部分較小的值跟右下部分較大的值，再分別搜尋左下部分跟右上部分。

Python3：

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        def search2D(rowStart, rowEnd, colStart, colEnd):
            if rowStart >= rowEnd or colStart >= colEnd:
                return False
            midRow = (rowStart + rowEnd) // 2
            left = colStart
            right = colEnd
            while left < right:
                mid = (left + right) // 2
                if matrix[midRow][mid] > target:
                    right = mid
                elif matrix[midRow][mid] < target:
                    left = mid + 1
                else:
                    return True
            return search2D(midRow+1, rowEnd, colStart, left) \
                or search2D(rowStart, midRow, left, colEnd)

        return search2D(0, len(matrix), 0, len(matrix[0]))

if __name__ == '__main__':
    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 = 31

    ans = Solution().searchMatrix(matrix, target)
    print(ans)

C：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
    bool search2D(int rowStart, int rowEnd, int colStart, int colEnd) {
        if (rowStart >= rowEnd || colStart >= colEnd)
            return false;
        int midRow = (rowStart + rowEnd) / 2, left = colStart, right = colEnd;
        while (left < right) {
            int mid = (left + right) / 2;
            if (matrix[midRow][mid] > target)
                right = mid;
            else if (matrix[midRow][mid] < target)
                left = mid + 1;
            else
                return true;
        }
        return search2D(midRow+1, rowEnd, colStart, left)
            || search2D(rowStart, midRow, left, colEnd);
    }
    return search2D(0, matrixSize, 0, matrixColSize[0]);
}

int main()
{
    int data[5][5] = {{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}};
    int matrixSize = 5;
    int * matrixColSize = (int*)malloc(sizeof(int) * matrixSize);
    int ** matrix = (int**)malloc(sizeof(int*) * matrixSize);
    for (int i = 0; i < matrixSize; i++) {
        matrixColSize[i] = 5;
        matrix[i] = (int*)malloc(sizeof(int) * 5);
        for (int j = 0; j < matrixColSize[i]; j++)
            matrix[i][j] = data[i][j];
    }
    int target = 19;
    
    bool ans = searchMatrix(matrix, matrixSize, matrixColSize, target);
    printf("%s\n", ans ? "True" : "False");
    return 0;
}

###### tags: `leetcode` `array` `matrix` `divide and conquer` `binary search`