Search a 2D Matrix

描述

Write an efficient algorithm that searches for a value in an m × 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. [
  2.   [1,   3,  5,  7],
  3.   [10, 11, 16, 20],
  4.   [23, 30, 34, 50]
  5. ]

Given target = 3, return true.

分析

二分查找。

代码

  1. // Search a 2D Matrix
  2. // 时间复杂度O(logn)，空间复杂度O(1)
  3. public class Solution {
  4.     public boolean searchMatrix(int[][] matrix, int target) {
  5.         if (matrix.length == 0) return false;
  6.         final int  m = matrix.length;
  7.         final int n = matrix[0].length;
  9.         int first = 0;
  10.         int last = m * n;
  12.         while (first < last) {
  13.             int mid = first + (last - first) / 2;
  14.             int value = matrix[mid / n][mid % n];
  16.             if (value == target)
  17.                 return true;
  18.             else if (value < target)
  19.                 first = mid + 1;
  20.             else
  21.                 last = mid;
  22.         }
  24.         return false;
  25.     }
  26. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/search/search-a-2d-matrix.html