用C语言查找subMatrix的左上角索引

Question

我要写一个高效的日志n-二进制搜索算法。程序是用c语言编写的，问题是:例如，我们有这样的矩阵：

                  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's的subMatrix的左上角索引，并返回它的行和值。函数头是: void getUpperLeft(int，int，int* getUpperLeft，int* getUpperLeft)。

我的方法是进入大矩阵的最后一行和最后一列，用二进制搜索找到“1”的第一个索引。这样我就可以计算出小矩阵的大小。然后我可以做大尺寸的垫子子大小垫子来找到左上角的索引。

在此之后，我可以用: pRow =(楼层)( index / col) pCol = index % col提取行和行索引。

我的代码还没有完成，因为我认为它变得太复杂了。

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);
    }
}

С，你建议一个更好的方法吗？

Answer 1

您可以首先创建一个通用的二进制搜索函数。这只需占用一个内存块并搜索第一个非零值，检查每个stride元素。

int FindFirstNonZero(const int* mem, int n, int stride)
{
    int left = 0, right = (n-1);
    while (left < right)
    {
        int mid = (left + right) / 2;
        if (mem[mid * stride] == 0)
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
    return mem[left * stride] != 0 ? left : n;
}

在这种情况下，执行任务所需的两个二进制搜索是非常直接的。首先，正如您所说的，查看最后一行并找到列。如果什么也找不到，那么函数就会失败。否则，您将对该列执行搜索(使用N的步幅)以获得行：

int GetUpperLeft(int mat[][N], int* row, int* col)
{
    int found = 0;
    int c = FindFirstNonZero(mat[N-1], N, 1);
    if (c != N)
    {
        *row = FindFirstNonZero(&mat[0][c], N, N);
        *col = c;
        found = 1;
    }
    return found;
}

名称如下：

int main()
{
    int mat[][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 = -1, col = -1;
    int ok = GetUpperLeft(mat, &row, &col);
    printf("ok=%d row=%d col=%d\n", ok, row, col);
}