January 21st, 2013, 05:55 AM

Binary search in a 2d
hi,
i'm new to programming and i have an assignment i can't figure out.
i need to determine if an integer is in a 2d array of N*N. the array is sorted:
90 92 93 99
23 57 76 80
1 4 6 9
and the time complexity has to be O(log(n)).
HOW?
thanks lol
January 21st, 2013, 06:05 AM

Do the rows overlap at all?
Given
A x x x B
C x x x D
E x x x F
B is always > C
D is always > E
And A C E is always sorted as well?
Then it's a binary search to find the row, then another binary search within the row.
January 21st, 2013, 06:08 AM

hi,
yes everything is perfectly sorted :)
and still, how do i preform the search?
sorry if it seems like a dumb question...
January 21st, 2013, 07:57 AM

Well if it were me, I'd use the bsearch library function.
But I'm going to guess that it's your homework to implement a bsearch, so I'd say start with typing "binary search" into a search engine, and doing a bit of reading.
Say perhaps the Wikipedia entry for a start.
Try and implement something simple, like a bsearch on a 1D array and post back when you have code (and are stuck).
January 21st, 2013, 10:07 AM

ok so i've been able to write some piece of code. everything works excapt for the number 54. any explanation?
Code:
#define N 6 /*the number of rows and columns and in the matrix*/
/*
the function will recive a sorted matrix(a matrix in which the numbers in each row are greater then the previous row and greater then the numbers before them) and will check if a searched number is there.
*/
int search_matrix(int a[N][N], int x);
int main()
{
int x,rc;
int matrix[N][N]={{93,94,96,97,99,104},{75,80,81,82,85,87},{54,65,66,68,70,73},{35,37,38,40,43,50},{14,16,19,20,31,33},{3,4,7,8,10,12}};
printf("Hi, This will help you search an integer in a matrix\nPlease enter an integer:\n");
rc=scanf("%d",&x);
if(rc!=1)
{
printf("Error!You didn't enter an integer!\n");
return 1;
}
printf("The result is %d\n",search_matrix(matrix,x));
return 0;
}
int search_matrix(int a[N][N], int x)
{
int mid ,max=0,min=N1,row;
while (max <= min)
{
mid=(max+min)/2;
if(x<a[N1][0])
{
row=N1;
break;
}
else if (x<=a[mid][0])
{
max = mid;
if (x > a[mid+1][0])
{
row=mid+1;
break;
}
if (x == a[mid+1][0])
{
row=mid+1;
break;
}
}
else if (x>=a[mid][0])
{
min = mid;
if (x < a[mid1][0])
{
row=mid;
break;
}
if (x == a[mid1][0])
{
row=mid1;
break;
}
}
}
max=N1;
min=0;
printf("%d\n",row);
while (max >= min)
{
mid=(max+min)/2;
if(a[row][mid]<x)
min = mid + 1;
else if(a[row][mid] > x )
max = mid  1;
else if(a[row][mid]==x)
return 1;
}
return 0;
}
January 21st, 2013, 01:48 PM

> everything works excapt for the number 54. any explanation?
a) add some prints to the code, like
Code:
mid = (max + min) / 2;
printf("Max=%d, Min=%d, mid=%d\n", max, min, mid );
If you put similar 'debug' printf statements through the code, you can work out the path that it takes.
b) Use a debugger, set a breakpoint on search_matrix, then singlestep through the code. When the code jumps to somewhere you don't expect, or a variable has an unexpected value, you've found a bug!
I do know that if you enter 54, you end up searching the wrong row of the matrix.
January 23rd, 2013, 10:01 AM
