Accepted C++ answer using upper_bound and binary_search, but it's slow, why?


  • 0
    J

    My logarithmic time algorithm is accepted but it costs 45ms. It's quite slow according to the histogram. Can anyone tell me why this code is slow? Thanks in advance.

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
    	auto search_this_row = upper_bound(matrix.begin(), matrix.end(), target,
    		[](const int val, const vector<int> &v) {
    			return val < v[0];
    		}
    	);
    	if (search_this_row == matrix.begin()) {
    		return false;
    	}
    	--search_this_row;
    	return binary_search(search_this_row->begin(), search_this_row->end(), target);
    }

Log in to reply
 

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