12ms binary search C++ solution


  • 0
    C
    class Solution {
    public:
    	int biSearchMatrix(vector<vector<int>>& matrix, int target){
    		int left = 0, right = matrix.size();
    		while (left < right){
    			int mid = left + (right - left) / 2;
    			if (matrix[mid][0] <= target)
    				left = mid + 1;
    			else
    				right = mid;
    		}
    		
    		return right - 1;
    	}
    	bool biSearchVector(vector<int>& nums,int target){
    		if (nums.empty())
    			return false;
    		int left = 0, right = nums.size() - 1;
    		while (left < right){
    			int mid = left + (right - left) / 2;
    			if (nums[mid]<target)
    				left = mid + 1;
    			else
    				right = mid;
    		}
    		return nums[right] == target;
    
    	}
    	bool searchMatrix(vector<vector<int>>& matrix, int target) {
    		int rowIndex = biSearchMatrix(matrix,target);
    		if (rowIndex < 0)
    			return false;
    		else
    			return biSearchVector(matrix[rowIndex], target);
    	}
    };
    

Log in to reply
 

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