# 9ms C++ solution without binary reseach, beats 100%

• Idea is very straight forward. Actually you can put start point on either top right or bottom left. I chose top right in this case.

``````bool searchMatrix(vector<vector<int>>& matrix, int target) {
int  i = 0, j = matrix[0].size()-1;
while (j >= 0 && i < matrix.size()) {
if (matrix[i][j] == target) {
return true;
}
else if (matrix[i][j] > target) {
j--;
}
else {
i++;
}
}
return false;
}
``````

I have no idea why it is even faster than binary search, the worst case of my solution is O(sqrt(m^2 + n^2)) which should be mathematically slower than O(log(mn)), may be it's just fast on those test cases :)

Also came up a binary search solution for 12 ms, hope this helps~

``````bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int left = 0, right = m*n-1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (matrix[mid/n][mid%n] == target) {
return true;
}
else if (matrix[mid/n][mid%n] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return false;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.