Guest User

Searching in a sorted 2D matrix

a guest
Apr 1st, 2014
215
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //I think I read this in a book somewhere, but it seems like a very elegant solution. Typing from memory, so this may or may not work as-is.
  2.  
  3. public boolean findElem(int matrix[][], int elem)
  4. {
  5. int rows = matrix.length;
  6. int cols = matrix[0].length;
  7. int start = 0;
  8. int end = rows*cols - 1;
  9.  
  10. while(start<= end)
  11.  {
  12.   int mid = start + (end-start)/2;
  13.   int row = mid/cols;
  14.   int col = mid% cols;
  15.   int curElem = matrix[row][col];
  16.   if(curElem == elem)
  17.      return true;
  18.   if(curElem > elem)
  19.      end = mid - 1;
  20.   else
  21.      start = mid + 1;
  22.  }
  23. return false;
  24. }
RAW Paste Data