C++ 使用行列指针在已排序的二维数组中进行二分查找

发布于07月04日

我正在try 构建一个使用二进制搜索在已排序的2D数组中查找数字的函数，我得到了这个无法更改的函数原型:

int findNum(int array[N][M], int num,unsigned int* row, unsigned int* col);

我试过这个:

int findNum(int array[N][M], int num,unsigned int* row, unsigned int* col){
    int low = 0 , mid , high = N*M - 1;

    while (low <= high)
    {
        mid = (low + high)/2;
        row = (mid / N);
        col = (mid % M);

        if (num < *(array + row + col)){
            high = mid - 1;
        }
        else if (num > *(array + row + col)){
            low = mid + 1;
        }
        else{
            return 1;
        }
    }
     
    return 0;
}

显然这是错误的，因为指针加指针是不允许的(*(array + row + col)).我不能更改函数原型，所以我必须使用行/列指针.我认为我使用row = (mid / N);和col = (mid % M);的方式也是错误的，因为它们一边是指针，另一边只是整数.

我怎么才能解决这个问题呢？

推荐答案

row和col看起来像指向整数的指针，如果函数找到值，则应该用要搜索的值的位置填充整数.

类似于:

#include <stdio.h>

#define N 3
#define M 3

int findNum(int array[N][M], int num, unsigned int *row, unsigned int *col)
{
    int low = 0, mid, high = N * M - 1;

    while (low <= high) {
        mid = (low + high) / 2;
        *row = (mid / N);
        *col = (mid % M);

        if (num < array[*row][*col]) {
            high = mid - 1;
        } else if (num > array[*row][*col]) {
            low = mid + 1;
        } else {
            return 1;
        }
    }

    return 0;
}

int main(void)
{
    int data[N][M] = {
        { 1, 2, 3 },
        { 4, 5, 6 },
        { 7, 8, 9 }
    };

    unsigned int r, c;

    if (findNum(data, 4, &r, &c)) {
        printf("R: %u C: %u\n", r, c);
    } else
        puts("Not found.");
}

输出: