74 Search a 2D Matrix
===

###### tags: `Medium`,`Array`,`Binary Search`

[74. Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/)

### 題目描述

You are given an `m x n` integer matrix `matrix` with the following two properties:

* Each row is sorted in non-decreasing order.
* The first integer of each row is greater than the last integer of the previous row.

Given an integer `target`, return `true` *if* `target` *is in* `matrix` *or* `false` *otherwise*.

You must write a solution in `O(log(m * n))` time complexity.

### 範例

**Example 1:**


Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

**Example 2:**


Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

**Constraints**:

* `m` == `matrix.length`
* `n` == `matrix[i].length`
* 1 <= `m`, `n` <= 100
* -10^4^ <= `matrix[i][j]`, `target` <= 10^4^

### 解答

#### C#

public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        int m = matrix.Length;
        int n = matrix[0].Length;

        int left = 0;
        int right = m * n - 1;

        while (left <= right) {
            int mid =  left + (right - left) / 2;
            (int i, int j) = Math.DivRem(mid, n); 

            if (matrix[i][j] > target) {
                right = mid - 1;
            } else if (matrix[i][j] < target) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        
        return false;
    }
}

> [name=Jim][time=Aug 7, 2023]

#### C++

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        return binarySearch(matrix, target, m, n);
    }

    bool binarySearch(vector<vector<int>>& matrix, int target, int m, int n) {
        int left = 0, right = m * n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int r = mid / n;
            int c = mid % n;
            if (matrix[r][c] == target) {
                return true;
            } else if (matrix[r][c] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return false;
    }
};

> [name=Jerry Wu][time=7 August, 2023]

#### Javascript

function searchMatrix(matrix, target) {
  const m = matrix.length;
  const n = matrix[0].length;

  let min = 0;
  let max = m * n - 1;

  while (max >= min) {
    const mid = (max + min) >> 1;
    const midVal = matrix[~~(mid / n)][mid % n];

    if (midVal === target) return true;

    if (midVal > target) {
      max = mid - 1;
    } else {
      min = mid + 1;
    }
  }

  return false;
}

> [name=Marsgoat][time=Aug 7, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)