力扣hot100——搜索二维矩阵

标题链接：搜索二维矩阵

固然本题利用二分法，但二分的写法有很多种，以是在判定 target 巨细与有序部门的关系的时间大概会出现细节上的差异。

1、 本题则是与常用代码差别的是：

else if(target<matrix[midRow][columnR])
{
rowH=midRow+1; //本题要改为rowH=midRow,
}
else{
rowL=midRow+1;
}
由于当target<matrix[midRow][columnR]时，target是小于midRow这一行的最右侧的最大元素，而这一行的其他比最右侧元素小的元素与target的关系未知。以是，应该rowH=midRow,而不是rowH=midRow+1。这是为了防止target在矩阵中存在，但是没有搜索到。

2、另一个差别的地方就是二分法的停止条件要从while(l<=r)改为while(l<r)。这是为了防止l大概r越上界大概下界。

c++代码实现

1. class Solution {
2. public:
3.     bool searchMatrix(vector<vector<int>>& matrix, int target) {
4.         int columnL=0,columnR=matrix[0].size()-1;
5.         int rowL=0, rowH=matrix.size()-1;
6.         if(columnR==0 && rowH==0)
7.         {
8.             if(matrix[0][0]==target)
9.             {
10.                 return true;
11.             }
12.             else{
13.                 return false;
14.             }
15.         }
16.         while (rowL<rowH)
17.         {
18.             int midRow = (rowL+rowH)/2;
19.             if(target == matrix[midRow][columnR])
20.             {
21.                 return true;
22.             }
23.             else if(target<matrix[midRow][columnR])
24.             {
25.                 rowH=midRow;
26.             }
27.             else{
28.                 rowL=midRow+1;
29.             }
30.         }
31.         if(matrix[rowL][columnL]==target)
32.         {
33.             return true;
34.         }
35.         
36.         //处理行：rowL行
37.         while(columnL<columnR)
38.         {
39.             int midColumn=(columnL+columnR)/2;
40.             if(target==matrix[rowL][midColumn])
41.             {
42.                 return true;
43.             }
44.             else if(target<=matrix[rowL][midColumn]){
45.                 columnR=midColumn;
46.             }
47.             else{
48.                 columnL=midColumn+1;
49.             }
50.         }  
51.         if(matrix[rowL][columnL]==target)
52.         {
53.             return true;
54.         }
55.         return false;
56.     }
57. };

复制代码