I'm trying to build a function that uses binary search to find a number in a sorted 2d array and I'm given this function prototype that I can't change:
int findNum(int array[N][M], int num,unsigned int* row, unsigned int* col);
I tried this:
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;
}
Apparently it's wrong because pointer plus pointer is not allowed (*(array + row + col)
). I can't change the function prototype so I have to use the row / column pointers. I think it's also wrong how I used row = (mid / N);
and col = (mid % M);
because on one side they are pointers and the other just integers.
How can I fix this?
row
and col
look like pointers to integers that should be populated with the position of the value being searched for, given the function finds the value.
Something like:
#include <stdio.h>
#define N 3
#define M 3
int findNum(int array[N][M], int num, unsigned int *row, unsigned int *col)
{
unsigned int low = 0, mid, high = N * M - 1;
while (low <= high) {
mid = (low + high) / 2;
unsigned int r = (mid / N);
unsigned int c = (mid % M);
if (num < array[r][c]) {
high = mid - 1;
} else if (num > array[r][c]) {
low = mid + 1;
} else {
if (row)
*row = r;
if (col)
*col = c;
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.");
}
Output:
R: 1 C: 0