Safe binary search implementation


  • 4
    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;
        }
    };

  • 0
    E

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


  • 0
    F
    
    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;
        }
    };

Log in to reply
 

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