【LeetCode從零單刷】Search a 2D Matrix

【LeetCode從零單刷】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.

  解答：

  因為排序過，思路很清晰。建立每行首元素的索引，然後行二分搜索，最後列二分搜索。復雜度是O(lg(m) + lg(n))。但是難點在於細節：

   

  這裡的搜索可能 False，也就是找不到元素。因此，如果 first = 1，last = 2，mid = (first + last)/2 = 1。下一次如果 first = mid = 1，又陷入了循環；因為除法取整的原因，有可能 last 一直無法取到。如果 first = 1，last = 2，mid = (first + last)/2 = 1。下一次如果 first = mid = 1，還是取不到 last = 2 的值。因此需要多判斷一次 last 的值；關於每行首元素的索引中的搜索，不同於列搜索。即使 target > 索引中的最大值，還是有可能存在此元素。例如 target = 30 > 23，依然存在

  class Solution {
  public:
      bool searchMatrix(vector>& matrix, int target) {
          vector rowfirst;
          for(int i=0; i rowfirst[tail])  head = tail;
              else if(target == rowfirst[mid] || target == rowfirst[tail])  return true;
              else if(target < rowfirst[mid])   tail = mid;
              else if(target > rowfirst[mid])   head = mid;
          }
          if(head > tail) return false;
          
          int first = 0;
          int last  = matrix[0].size() - 1;
          while(first <= last){
              if(first == last || first + 1 == last){
                  if (matrix[head][first] == target || matrix[head][last] == target)   return true;
                  else    return false;
              }
              int mid = (first + last) / 2;
              if(target == matrix[head][mid] || target == matrix[head][last])   return true;
              else if(target < matrix[head][mid])   last = mid;
              else if(target > matrix[head][mid])   first = mid;
          }
          return false;
      }
  };