剑指 Offer 04. 二维数组中的查找

题目

代码

#include <iostream>
#include <vector>
using namespace std;

bool searchBinary(vector<int> nums, int target){
    
	int left = 0, right = nums.size() - 1;
	while(left <= right){
    
		int mid = left + (right - left) / 2;
		if(nums[mid] == target){
    
			return true;
		}else if(nums[mid] < target){
    
			left = mid + 1;
		}else if(nums[mid] > target){
    
			right = mid - 1;
		}
	}
	return false;
}

bool findNumberIn2DArray(vector<vector<int> >& matrix, int target) {
    
	int n = matrix.size();
	if(n == 0){
    
		return false;
	}
	int m = matrix[0].size();
	if(m == 0){
    
		return false;
	}
	bool res;
	for(int i = 0; i < n; i++){
    
		if(matrix[i][0] > target){
    
			return false;
		}else if(matrix[i][0] <= target && target <= matrix[i][m-1]){
    
			res = searchBinary(matrix[i], target);	
			if(res){
    
				return true;
			}
		}
	}
	return false;
}

int main(){
    
	int n, m, target;
	bool res;
	cin>>n>>m>>target;
	vector<vector<int> > matrix(n, vector<int>(m));
	for(int i = 0; i < m; i++){
    
		for(int j = 0; j < n; j++){
    
			cin>>matrix[i][j];
		}
	}
	res = findNumberIn2DArray(matrix, target);
	if(res){
    
		cout<<"true";
	}else{
    
		cout<<"false";
	}
	return 0;
}