基于二分查找(log n复杂度)的C语言子矩阵左上角索引求解问询

需要用C语言实现时间复杂度为O(log n)的二分查找算法，在给定矩阵中找到全为1的子矩阵的左上角行、列索引，函数定义为void getUpperLeft(int mat[][N], int n, int* row, int* col)。

示例矩阵：

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 1 1 1
0 0 0 0 1 1 1
0 0 0 0 1 1 1
0 0 0 0 1 1 1

本人思路为在矩阵最后一行和最后一列通过二分查找找到第一个1的索引，计算子矩阵大小后推导左上角索引，但代码实现过于复杂且未完成，现寻求更优实现方案。未完成代码如下：

void getupperLeft(int mat[][N], int n, int* row, int* col)
{
    int* startRow = mat[0][N - 1];
    int* endRow = mat[N - 1][N - 1];
    int* startCol = mat[N - 1][0];
    int* endCol = mat[N - 1][N - 1];

    int* pCol;
    int* pRow;

    while (startRow <= endRow)
    {
        int middleRow = (*startRow + *endRow - N) / 2;
        int currentRow = middleRow / N;
        int currentCol = middleRow % N;

        if (*(mat + N * currentRow + currentCol) == 0 &&
            *(mat + ((currentRow + 1) * N) + currentCol) == 1)
        {
            *pRow = currentRow + 1 * N;
        }

        else if (*(mat + N * currentRow + currentCol) == 1 &&
            *(mat + ((currentRow - 1) * N) + currentCol) == 0)
        {
            *pRow = currentRow;
        }
        else
            startRow = (currentRow + 1 * N);
    }
}

核心思路 #

不需要同时处理行和列的复杂指针计算，可分别对最后一列和最后一行做二分查找，直接定位全1子矩阵的起始边界：

• 对最后一列二分，找到最上方的1所在行，即为全1子矩阵的起始行
• 对最后一行二分，找到最左侧的1所在列，即为全1子矩阵的起始列
• 由于矩阵中全1区域是连续矩形，上述两个坐标的交点就是左上角索引

代码实现 #

#include <stdio.h>

#define N 7

// 二分查找最后一列中第一个1的行索引
int findFirstRow(int mat[][N], int n) {
    int left = 0, right = n - 1;
    int result = n; // 默认设为n，题目保证存在全1子矩阵，实际会被覆盖
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (mat[mid][n-1] == 1) {
            result = mid;
            right = mid - 1; // 继续向上找更早出现的1
        } else {
            left = mid + 1;
        }
    }
    return result;
}

// 二分查找最后一行中第一个1的列索引
int findFirstCol(int mat[][N], int n) {
    int left = 0, right = n - 1;
    int result = n;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (mat[n-1][mid] == 1) {
            result = mid;
            right = mid - 1; // 继续向左找更早出现的1
        } else {
            left = mid + 1;
        }
    }
    return result;
}

void getUpperLeft(int mat[][N], int n, int* row, int* col) {
    *row = findFirstRow(mat, n);
    *col = findFirstCol(mat, n);
}

// 测试示例
int main() {
    int mat[N][N] = {
        {0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0},
        {0,0,0,0,1,1,1},
        {0,0,0,0,1,1,1},
        {0,0,0,0,1,1,1},
        {0,0,0,0,1,1,1}
    };
    int row, col;
    getUpperLeft(mat, N, &row, &col);
    printf("左上角坐标：行%d，列%d\n", row, col); // 输出：行3，列4
    return 0;
}

代码说明 #

1. 时间复杂度：两次二分查找，每次复杂度为O(log n)，总时间复杂度O(log n)，符合要求
2. 逻辑简化：拆分行、列查找逻辑，避免指针操作混乱，代码可读性更高
3. 边界处理：通过right = mid -1不断逼近第一个1的位置，确保找到的是最上方/最左侧的有效边界

内容的提问来源于stack exchange，提问作者Trubadurpoman