### Thread: Binary search in a 2d

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jan 2013
Posts
9
Rep Power
0

#### 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
2. 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.
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jan 2013
Posts
9
Rep Power
0
hi,

yes everything is perfectly sorted :)

and still, how do i preform the search?

sorry if it seems like a dumb question...
4. 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).
5. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jan 2013
Posts
9
Rep Power
0
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}};
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=N-1,row;
while (max <= min)
{
mid=(max+min)/2;
if(x<a[N-1][0])
{
row=N-1;
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[mid-1][0])
{
row=mid;
break;
}
if (x == a[mid-1][0])
{
row=mid-1;
break;
}
}
}
max=N-1;
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;
}```
6. > 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 single-step 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.
7. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jan 2013
Posts
9
Rep Power
0
thanks!