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?
>Solution :
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)
{
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.");
}
Output:
R: 1 C: 0