240-搜索二维矩阵 II

题目

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

思路

1. 线性搜索：

   从右上往左下搜索。如果比右上大，就去下一行。如果比下一行小，就去该行左侧。

2. 二分搜索

   指定左右、上下边界，与边界中心进行比较。

   • 如果比边界中心小：去中心左侧和上侧搜索。
   • 如果比边界中心大：去中心右侧和下侧搜索。

代码

1. 线性搜索

   class Solution {
   public:
       bool searchMatrix(vector<vector<int>>& matrix, int target) {
           int y = 0,x = matrix[0].size()-1;
           for(;y<matrix.size()&&x>=0;){
               if(matrix[y][x]==target) return true;
               if(matrix[y][x]<target) y++;
               else x--;
           }
           return false;
       }
   }

2. 二分搜索

   class Solution {
   public:
       bool searchMatrix(vector<vector<int>>& matrix, int target) {
           int m = matrix.size(), n = matrix[0].size();
           return searchMatrix(matrix,target,0,m-1,0,n-1);
       }
       bool searchMatrix(vector<vector<int>>& matrix,int target,int ru,int rd,int cl,int cr){
           if(ru>rd||cl>cr) return false;
           int rm = (ru+rd)/2, cm = (cl+cr)/2;
           if(matrix[rm][cm]==target) return true;
           else if(matrix[rm][cm]>target){
               return searchMatrix(matrix,target,ru,rm-1,cl,cr)||
               searchMatrix(matrix,target,ru,rd,cl,cm-1);
           }else{
               return searchMatrix(matrix,target,ru,rd,cm+1,cr)||
               searchMatrix(matrix,target,rm+1,rd,cl,cr);
           }
       }
   };