二维数组中的查找

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

解题思路1

以左下角元素为起点，进行比较； 大往左移，小往上移。
时间复杂度：O(行高 + 列宽)

  public boolean Find(int target, int [][] array) {
      int row = array.length - 1;
      int col = 0;
      while(row>=0 && col<=array[0].length-1) {
          if(target == array[row][col]) {
              return true;
          } else if(target > array[row][col]) {
              col++;
          } else {
              row--;
          }
      }
      return false;
  }

解题思路2：

把每一行看成有序递增的数组，利用二分查找，通过遍历每一行得到答案
时间复杂度：O(nlogn)

 public boolean Find(int target, int [][] array) {
      int row = 0;
      while (row <= array.length - 1) { 
          int low = 0;
          int high = array[0].length-1;
          while(low <= high) {
              int middle = (low + high) / 2;
              if(target == array[row][middle]) {
                  return true;
              } else if(target > array[row][middle]) {
                  low = middle + 1;
              } else {
                  high = middle - 1;
              }
          }
          row ++;
       }
      return false;
  }

总结
关于查找类型的题，要先关注给定的数据是否有序；如果有序，则要看看是否利用有序的特点，应用特殊的解法。如：二分查找，找特殊起始点等