# 74. Search a 2D Matrix

### Description

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.

### **Constraints**

### **Approach**

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/search-a-2d-matrix)
* ProgramCreek

### Examples

{% tabs %}
{% tab title="Example 1" %}
**Input:**

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

target = 30

**Output:** true
{% endtab %}

{% tab title="Example 2" %}
**Input:**

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

target = 13

**Output:** false
{% endtab %}
{% endtabs %}

### Solutions

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(log(mn)) since it's a standard binary search.
 * Space complexity : O(1).
 */

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        if(row == 0) return false;
        int col = matrix[0].length;
        if(col == 0) return false;
        for(int[] arr: matrix) {
            if(target <= arr[col-1]) {
                if(arr[col-1] == target || binarySearch(arr, col, target) != -1) {
                    return true;
                }
                break;
            }
        }
        return false;
    }
    private int binarySearch(int[] arr, int n, int target) {
        int low = 0;
        int high = n-1;
        while(low <= high) {
            int mid = (low+high)/2;
            if(arr[mid] == target) {
                return mid;
            } else if(target > arr[mid]) {
                low = mid+1;
            } else {
                high = mid-1;
            }
        }
        return -1;
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(log(mn)) since it's a standard binary search.
 * Space complexity : O(1).
 */
 
 class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        if(row == 0) return false;
        int col = matrix[0].length;
        
        // Binary search
        int low = 0, high = row*col-1;
        int pivotIdx, pivotValue;
        while(low <= high) {
            pivotIdx = (low+high)/2;
            pivotValue = matrix[pivotIdx/col][pivotIdx%col];
            if(target == pivotValue) {
                return true;
            } else if(target < pivotValue) {
                high = pivotIdx-1;
            } else {
                low = pivotIdx+1;
            }
        }
        return false;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*