# Safe binary search implementation

• ``````class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
/** first check whether it is in the range **/
int m=matrix.size(), n=matrix[0].size();
if(target<matrix[0][0] || target>matrix[m-1][n-1]) return false;

int start=-1, end=m*n-1;
while(end-start>1){
int mid=(start+end)/2;
if(matrix[mid/n][mid%n] >= target) end=mid;
else start=mid;
}

return matrix[end/n][end%n]==target;
}
};``````

• Not safe! Can you image what will happen if start + end > 0x7fffffff?

• ``````
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int row = matrix.size(), col = matrix[0].size();
if (target < matrix[0][0] || target > matrix[row-1][col-1]) return false;
int left = 0, right = row*col - 1;
while (right > left) {
int mid = left + (right - left) / 2;
if (matrix[mid/col][mid%col] < target) left = mid + 1;
else right = mid;
}
return matrix[right/col][right%col] == target;
}
};``````

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