剑指offer系列题笔记（二维数组的查找）

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

/*
  给定的数组从左到右是递增有顺序的，所以查找问题一般用二分查找。
  这个程序的时间复杂度是MlogN
*/
class Solution {
public:
  bool Find(int target, vector<vector<int> > array) {
    int row = array.size();
    int col = array[0].size();
    /*边界条件1：当输入的二维数组的行或列为空时，直接返回false*/
    if (row == 0 || col == 0) { return false; }
    /*边界条件2：当输入的target过小或者过大时，直接返回false  */
    if (target < array[0][0]) { return false; }
    if (target > array[row - 1][col - 1]) { return false; }
    /*对输入数组的每一行进行二分查找*/
    for (int i = 0; i < row; i++) {
      int l = 0, r = col - 1;
      while (l <= r) {
        int m = (l + r) / 2;
        if (array[i][m] == target) {
          return true;
        }
        else if (target > array[i][m]) {
          l = m + 1;
        }
        else {
          r = m - 1;
        }
      }
    }
    /*程序运行到这里，说明二维数组中没有target，返回false*/
    return false;
  }
};