leetCode 74.Search a 2D Matrix(搜索二維矩陣) 解題思路和方法

leetCode 74.Search a 2D Matrix(搜索二維矩陣) 解題思路和方法

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

   

  For example,

  Consider the following matrix:

  [
    [1,   3,  5,  7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
  ]
  

  Given target = 3, return true.

  思路：此題還是比較簡單的，主要是用兩個二分法，才對第一列使用，再對特定的行使用。

  具體代碼如下：

   

  public class Solution {
      public boolean searchMatrix(int[][] m, int target) {
          //兩個二分搜索
          //先搜索第一列，找到確定的行，然後再搜索行
          int i = 0;
          int j = m.length-1;
          int mid = 0;
          //搜尋第一列
          while(i <= j){
              mid = (i + j)/2;
              if(m[mid][0] == target){
                  return true;
              }else if(m[mid][0] < target){
                  i = mid + 1;
              }else{
                  j = mid - 1;
              }
          }
          if(m[mid][0] > target){
              if(mid == 0){
                  return false;
              }
              mid--;//mid-1
          }
          //搜尋mid行
          i = 0;
          j = m[0].length -1;
          int k = mid;
          //搜尋到了返回true
          while(i <= j){
              mid = (i + j)/2;
              if(m[k][mid] == target){
                  return true;
              }else if(m[k][mid] < target){
                  i = mid + 1;
              }else{
                  j = mid - 1;
              }
          }
          //沒有搜尋到，返回false
          return false;
      }
  }