Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
January 21st, 2013, 05:55 AM
 daniig
Registered User

Join Date: Jan 2013
Posts: 9
Time spent in forums: 2 h 30 m 42 sec
Reputation 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
January 21st, 2013, 06:05 AM
 salem
Contributed User

Join Date: Jun 2005
Posts: 4,260
Time spent in forums: 2 Months 4 Weeks 1 Day 15 h 3 m 57 sec
Reputation Power: 1827
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.
__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper

#3
January 21st, 2013, 06:08 AM
 daniig
Registered User

Join Date: Jan 2013
Posts: 9
Time spent in forums: 2 h 30 m 42 sec
Reputation 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
January 21st, 2013, 07:57 AM
 salem
Contributed User

Join Date: Jun 2005
Posts: 4,260
Time spent in forums: 2 Months 4 Weeks 1 Day 15 h 3 m 57 sec
Reputation Power: 1827
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
January 21st, 2013, 10:07 AM
 daniig
Registered User

Join Date: Jan 2013
Posts: 9
Time spent in forums: 2 h 30 m 42 sec
Reputation 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,3  3},{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
January 21st, 2013, 01:48 PM
 salem
Contributed User

Join Date: Jun 2005
Posts: 4,260
Time spent in forums: 2 Months 4 Weeks 1 Day 15 h 3 m 57 sec
Reputation Power: 1827
> 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
January 23rd, 2013, 10:01 AM
 daniig
Registered User

Join Date: Jan 2013
Posts: 9
Time spent in forums: 2 h 30 m 42 sec
Reputation Power: 0
thanks!

 Viewing: Dev Shed Forums > Programming Languages > C Programming > Binary search in a 2d