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 921,621 Views |
(69 votes, avg: 4.07)
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.
Binary search diagonally find the number or you will end up with number smaller then key, move to next diagonal .
For second case binary search element in two array first one is
(0,C) (R,C)
(R,0) (R,C)
Complexity is logn + logm
There can be another approach…
think of any element near the center of the matrix…
if that element is greater than the search item… then, any element with row and col greater than the current element cannot have the search item…
similiarly if element is smaller than the search item… then, any element with row and col smaller than the current element cannot have the search item…
we will be eliminating approx 3/4 of the current matrix at each step…
In the next step, we get a sub-matrix… choose the middle element by
(rowup - rowlow)/2, (colup- coldown)/2
and can start all over again…
Note that this is a true binary search completely analogous to our linear binary search… so much so, that when we reach the stage when we have only one col or only one row left… we will actually be doing linear binary search
Code Decoder has the right idea:
Here is the details of the algorithm:
1 4 5 8 9 10
2 5 6 9 11 12
3 6 7 10 12 14
8 9 10 11 13 15
Suppose the number is 7.
First applied Binary Search on row 1, it takes O(log N),
if found, its done. If not, get the index of the element that is
less than 7. In this example, it is 2(0 to n-1).
Applied to column, with O(log M), we get index 2 also.
Now, we need only to continue the search on row 1 to 2 and column 1 to 2:
5 6
6 7
In the next iteration, each time, we either find 7 in the new first row
or new first row(not in this case). Again, it takes at most O(log N-1) plus
O(log M-1).
The complexity is O(M*logN) assuming M
if we apply binary search on each row we can also get O(n log m) where n = # rows and m = # cols. However I would have to agree with the O(m+n) solution is a superior choice.
I have a better answer. Consider the four co-ordinates of an array say top-left(tl), top-right(tr), bottom-left(bl), bottom-right(br)
Now when a number is given compare it with the four co-ordinates to check if it falls within the array(the range of co-ordinates), if not return not found.
If yes, then devide the array into four sub-parts(length/2, heigt/2), and compare the number with iteratively with all the four sub-cordinates of each sub-array. Discard arrays whose sub-cordinates range is not matching.
Recursively repeat the above step.
Leave an Answer/Comment