Skip to content

Instantly share code, notes, and snippets.

@nezahualcoyotl
Last active October 9, 2020 20:14
Show Gist options
  • Save nezahualcoyotl/838f0c2e8f1bdeae8ec3e54feaec0a93 to your computer and use it in GitHub Desktop.
Save nezahualcoyotl/838f0c2e8f1bdeae8ec3e54feaec0a93 to your computer and use it in GitHub Desktop.
Leetcode - Search a 2D Matrix solution in C#
/* This was my best approach to beat this problem.
It took me ages to get to it because I did it before
completely understanding binary search, but I got it
recognized by two engineers I admire so this is my way
of patting my own back and remembering the effort */
public class Solution {
public bool SearchMatrix(int[][] matrix, int target) {
if(matrix.Length == 0) return false;
int xMiddle = (matrix.Length-1)/2;
int yMiddle = (matrix[xMiddle].Length-1)/2;
int xLowerBound = 0;
int xUpperBound = matrix.Length-1;
int yLowerBound = 0;
int yUpperBound = matrix[xUpperBound].Length - 1;
while(xLowerBound <= xUpperBound && yLowerBound <= yUpperBound)
{
if( target < matrix[xMiddle][yMiddle] )
{
if(yMiddle == 0){
if(xMiddle == 0) return false;
xUpperBound = xMiddle - 1;
yUpperBound = matrix[xUpperBound].Length - 1;
} else {
yUpperBound = yMiddle - 1;
}
}
else if( target > matrix[xMiddle][yMiddle] )
{
if(yMiddle == matrix[xMiddle].Length-1){
if(xMiddle == matrix.Length-1) return false;
xLowerBound = xMiddle + 1;
yLowerBound = 0;
} else {
yLowerBound = yMiddle + 1;
}
}
else return true;
xMiddle = ((xUpperBound - xLowerBound)/2) + xLowerBound;
yMiddle = ((yUpperBound - yLowerBound)/2) + yLowerBound;
}
return false;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment