LeetCode热题100：二分

摘要

题目	知识点
240. 搜索二维矩阵 II - 力扣（LeetCode）	二分，二叉搜索树

搜索二维矩阵 ||

1）一次二分

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
	// 遍历第每一行 + 二分查找当前行
	bool searchMatrix(vector<vector<int>>& v, int t) {
		int n = v.size(), m = v[0].size();
		for(int i = 0 ; i < n ; i ++){
			if(binary_search(v[i].begin(), v[i].end(), t)) return true;
		}
		return false;
	}
};

2）两次二分

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
	bool bs(vector<vector<int>>& v, int y, int fx, int ex, int t){
		int l = fx-1;
		int r = ex;
		while(l+1 != r){
			int mid = (l+r)/2;
			if(v[mid][y] < t){
				l = mid;
			}else{
				if(v[mid][y] == t) return true;
				r = mid;
			}
		}
		return false;
	}
	
	bool searchMatrix(vector<vector<int>>& v, int t) {
		// 先用一次二分，找到最小的满足 <= t 条件的列
		int n = v.size(), m = v[0].size();
		int l = 0;
		int r = m;
		while(l+1 != r){
			int mid = (l+r)/2;
			if(v[0][mid] <= t){
				l = mid;
			}else{
				r = mid;
			}
		}
		// 遍历[0, l]的列
		for(int i = l ; i >= 0 ; i --){
			// 对每一列再进行一次二分查找
			if(bs(v, i, 0, n, t)) return true;
		}
		return false;
	}
};

3）二叉搜索树

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
	int n, m;
	
	bool inrange(int x, int y){
		if(x < 0 || x >= n) return false;
		if(y < 0 || y >= m) return false;
		return true;
	}
	// 以右上角(0, m-1)为起点
	// v[x-1][y] 和 v[x][y+1] 分别为左右子节点
	// 分别 对应 < 和 >
	// 之后按二叉搜索树查找即可
	bool searchMatrix(vector<vector<int>>& v, int t) {
		n = v.size(), m = v[0].size();
		int x = 0, y = m-1;
		while(inrange(x, y)){
			if(t == v[x][y]) return true;
			else if(t > v[x][y]){
				x++;
			}else if(t < v[x][y]){
				y--;
			}
		}
		return false;
	}
};