Bloomberg LP Interview Question Software Engineer / Developers
First using binary search on 0th row we will find out column in which element is present and then we will implement binary search on that column. so complexity = O(logn + logn) = O(logn).
This is not correct
what if the number is not in the arrange of the first row?
This problem could not be solved faster than O(max(m,n))
The following function performs the binary search on the Matrix whose elements are sorted, and returns the column position and row position of found element in elementrow;
int Matrix_binarysearch(int **dd,int row,int col,int k, int *elementrow)
{
int mid;
int low;
int high;
low=0;
high= row-1;
while(low<=high)
{
mid = (low + high)/2;
if(k < dd[mid][0])
{
high = mid -1;
} else if( k > dd[mid][col-1] )
{
low = mid+1;
}else
{
*elementrow = mid;
return Arrary_binarysearch(k,dd[mid],0,col-1);
}
}
return -1;
}
Start from the bottom right element of the Matrix, if it is less than the target element, go right; otherwise go upward of the Matrix. Continue this process until you find the element or you are out of the boudary of the Matrix.
ps: The code is easy, key point is to find out where to start searching
Personally I like this solution.
You could implement one in which you divide the matrix into quadrants, and check each possible quadrant.
std::pair<int, int>
searchNum(const matrix& mx, unsigned int x0, unsigned y0, unsigned int x1, unsigned int x2, int val)
{
// Check if we are there.
if (x0 == x1 && y0 == y1)
return (mx(x0, y0) == val) ? make_pair(x0, y0) : make_pair(-1,-1);
unsigned int xmid = x0 + ((x0 + x1) >> 1), ymid = y0 + ((y0 + y1) >> 1);
if (mx(xmid, ymid) == val)
return make_pair(xmid, ymid);
std::pair<int, int> res = make_pair(-1,-1);
// Now we check if number contained in quadrants.
// First.
if (mx(x0, y0) <= val && mx(xmid, ymid) => val)
{
res = searchNum(x0, y0, xmid - 1, ymid - 1);
if (res.first > 0)
return res;
}
// Second.
if (mx(x0, ymid + 1) < val && mx(xmid, yend) > val)
{
res = searchNum(x0, y0, xmid - 1, ymid - 1);
if (res.first > 0)
return res;
}
// Third.
if (mx(xmid + 1, y0) < val && mx(xend, ymid) > val)
{
res = searchNum(x0, y0, xmid - 1, ymid - 1);
if (res.first > 0)
return res;
}
// Fourth.
if (mx(xmid + 1, ymid + 1) < val && mx(xend, yend) > val)
{
res = searchNum(x0, y0, xmid - 1, ymid - 1);
if (res.first > 0)
return res;
}
}
It's possible for a number to be in 3 quadrants, so this has solution
T(n) = 3 * T(n/4) + O(1), which is O(n^log_4(3)), where n is the number of elements.
@wei:
i don't think my approach is wrong. I am not searching for element in the first row but i am searching for column in which element is present. You got that?
As the columns are also sorted we can check if element lies in that column. For e.g. if c[0] and c[n] are first and last element of column and e is the element we r searching for then e lies in that column if (c[0]<=e<=c[n])
What if you treat the matrix as an array
a[i][j] will translate to array[(i-1)*n + j]
and just perform a binary search on the Array above, that will give you O(log(n*N)) = O(2.log(n)) = O(log(n))
Notice the fact that for any j <= i, a[j][i] <= a [i][i], a[i][j] <= a[i][i]. We can first employ binary search to get the "_|" shape region which contains the number, then use binary search again to obtain the row and column of the number. The complexity should be O(logn)
Yep ... that's what I think too. Another issue also is that it is now not so clear how to choose the pivot. When we do binsearch on a 1D length n array, without more specific information we would just take the pivot to be around n/2. To do something similar for binsearch along a principal diagonal of the matrix we need to choose the pivot so that it subdivides the region into two approximately equal areas. The formula would take some working I think, involving the square-root of the dimensions.
Complexity : 4lg(n)
Do a binary search on the diagonal elements . Find two elements along the diagonal such that this number lies between the values of this elements.
Do a binary search on the rows and columns which runs through these two elements.
start at a point that: the elements at one its side follows different sorting sequence from another side. lets' say:
1 2 3 4
3 5 8 9
6 7 8 10
11 15 18 20;
in this case you choose either 4 or 11.
then if the current number is smaller than you expect, move towards decreasing side, else moves towards increasing side...
let's say you choose 4, you find 7.
first move down, then move left, then move left, then move down...
O(n)
straight out of cracking the coding interview. Copy pasting from the book directly:
Assumptions:
»»Rows are sorted left to right in ascending order. Columns are sorted top to bottom in ascending order.
»»Matrix is of size MxN.
This algorithm works by elimination. Every move to the left (--col) eliminates all the elements below the current cell in that column. Likewise, every move down eliminates all the elements to the left of the cell in that row.
- Yash August 25, 20131 boolean FindElem(int[][] mat, int elem, int M, int N) { 2 int row = 0; 3 int col = N-1; 4 while (row < M && col >= 0) { 5 if (mat[row][col] == elem) { 6 return true; 7 } else if (mat[row][col] > elem) { 8 col--; 9 } else { 10 row++; 11 } 12 } 13 return false; 14 }