Interview Questions And Answers 
-
How do you apply Binary Search on 2D array supposed you have 2D array with integers sorted both horizontally and vertically. If you find any occurrence of the value you are looking for you return true else false. What is the complexity?
For example the 2D array could look like the following
1 4 5 6
2 5 7 91,221 Views |
(8 votes, avg: 3.13)
Loading ...
Answers »
Our Sponsors
Our Sponsors
search diagonally.
diag 1 = 1
diag2 = 2,4
….
for example
given the number 7 we take the bounds of each diagonal and check wether the number will fall in that range else move farward.
here diagonal selection is sequential but the number search is binary.
//int uperrow,uppercol;
// number to b searched is n;
//asumed no are sorted in ascending order
1)apply binary search on 1st row of initial arrey,that ll return the index of smallest no >= n ,in that row i.e. upper bound of coloumns and is denoted as uppercol;
2)apply binary search on 1st col of initial arrey,that ll return the index of smallest no>=n, in that col i.e. upper bound of rows and is denoted as upperrow;
3)now ur matrix size is upperrow*uppercol;forget no beyond this range;
4)apply step 1) and 2) again but remember that matrix is shortened,so apply search remembering the upperbounds of rows n colunms;
None of the above will work. The best solution possible is is an O(m+n) solution.
Start with the left bottom element.
If it is smaller than key, move to the left.
If it is larger than the key, move upwards.
Continue till you find the key or reach a boundary.
Regards,
J1gs4w
Rimi > understood your logic but want to change a bit.
let firstrow,lastrow,firstcol,lastcol be the variable..
if (a[midrow][midcol] target)
{
lastrow=midrow
lastcol=modcol
}
Assuming the array has N rows and M columns, searching for the value V:
Perform binary search on the first row, and find the index i s.t. array[0,i-1]
I suggest following method to use….
First Search the no. in first row and store the index of the element which is just smaller than the no. to search. Similarly find the same in the first column. Now you have two indices this will divide the entire matrix into four parts out of which only one part will lie in our problem domain.
Apply the same logic for this part of matrix.
This way you can find the element in least time.
Leave an Answer/Comment