12ms C++ Two BinarySearch


  • 0
    C

    2 binary search. one to search which row. one to search if target is in that row.

    class Solution {
    public:
        bool searchRow(vector<int>& row, int st, int ed, int target)
        {
            if (st > ed)
            {
                return false;
            }
            else if (st == ed)
            {
                return (row[st] == target);
            }
            else
            {
                int mid = (st+ed)/2;
                
                if (row[mid] == target)
                {
                    return true;
                }
                else if (row[mid] > target)
                {
                    return searchRow(row, st, mid-1, target);
                }
                else
                {
                    return searchRow(row, mid+1, ed, target);
                }
            }
            
            return false;
        }
    
        bool searchMatrixRecur(vector<vector<int>>& matrix , int st, int ed, int target)
        {
            if (st > ed)
            {
                return false;
            }
            else if (st == ed)
            {
                return searchRow(matrix[st], 0, matrix[st].size()-1, target);
            }
            else
            {
                int mid = (st+ed)/2;
                int len = matrix[mid].size();
                
                if (matrix[mid][len-1] == target)
                {
                    return true;
                }
                else if (matrix[mid][len-1] > target)
                {
                    return searchMatrixRecur(matrix, st, mid, target);
                }
                else
                {
                    return searchMatrixRecur(matrix, mid+1, ed, target);
                }
            }
            
            return false;
        }
    
        bool searchMatrix(vector<vector<int>>& matrix, int target) 
        {
            return searchMatrixRecur(matrix, 0, matrix.size()-1, target);
        }
    };

Log in to reply
 

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