思路

由于矩阵中的数是排序好的，因此具有以下数据规律：

• 以要查找的数为中心，左上小于它，右下大于他

1 解一： 数组遍历

int i = 0, j = M - 1;
while (i < N && j > 0) {
  if (nums[i][j] == K) {
    System.out.println("Yes");
    return ;
  }
  else if (nums[i][j] > K) {
    j --;
  }
  else {
    i ++;
  }
}
System.out.println("No");

• 其中j -- 如果在改行找不到，则下一行，核心1

2 解二：二分查找

思路： 既然可以定位到数所在的行，可以在行内进行二分查找

2.1 Bug1

• 由于按照行有顺序，按照列也有顺序，但其不是逐行逐列递增的，因此不能说可以定位在哪一行，即不能使用行后最大的元素大于要查找的元素，就说要找的元素在该行，有可能在下一行
• 在else { 中， 如果找不到元素也会陷入本行的死循环中，而不会到下一行

int i = 0, j = M-1;
while(i < N) {
  if (nums[i][j] < K) {
    i++;
  }
  else {
    // 所要查找的数在本行
    int left = 0, right = j;
    while (left <= right) {
      int mid = (left + right) / 2;
      if (nums[i][mid] == K) {
        System.out.println("Yes");
        return ;
      }
      else if (nums[i][mid] < K) {
        left = mid + 1;
      }
      else {
        right = mid - 1;
      }
    }
  }
}
System.out.println("No");
}

2.2 Bug2

• 找不到，或者不满足条件，需要到下一行，在二分中，找不到的情况，永远在本行循环，陷入死循环else if (nums[i][j] > K){

int i = 0, j = M-1;
while(i < N) {
  if (nums[i][j] == K) {
    System.out.println("Yes");
    return;
  }
  else if (nums[i][j] > K){
    // 所要查找的数在本行
    int left = 0, right = j;
    while (left <= right) {
      int mid = (left + right) / 2;
      if (nums[i][mid] == K) {
        System.out.println("Yes");
        return;
      } else if (nums[i][mid] < K) {
        left = mid + 1;
      } else if (nums[i][mid] > K){
        right = mid - 1;
      }
    }
  }
  else {
    // 没有满足条件，下一行
    i++;
  }
}

2.3 正确二分查找代码

int i = 0, j = M-1;
while(i < N) {
  if (nums[i][j] == K) {
    System.out.println("Yes");
    return;
  }
  else if (nums[i][j] > K){
    // 所要查找的数在本行
    int left = 0, right = j;
    while (left <= right) {
      int mid = (left + right) / 2;
      if (nums[i][mid] == K) {
        System.out.println("Yes");
        return;
      } else if (nums[i][mid] < K) {
        left = mid + 1;
      } else if (nums[i][mid] > K){
        right = mid - 1;
      }
    }
  }
  // 没有找到，或者都不满足，直接在下一行查找
  i++;
}