Search a 2D Matrix

This question is asked at both Amazon and Microsoft. We want to write an efficient algorithm that searches for a value in an m x n matrix. The 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. 

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

Approach number 1 is the binary search, where one could notice that the input matrix m x n could be considered as a sorted array of length m x n. 

We assign left to the first element and right to the last element. Then we get the pivot index to the middle, and compare the element to target and adjust the element accordingly. This will be O(log n). 

Here is the final code:

class Solution {

    public boolean searchMatrix(int[][] matrix, int target) {

        int m = matrix.length;

        if (m == 0) return false;

        int n = matrix[0].length;

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

        int pivotIdx, pivotElement;

        while(left <= right) {

            //calculate a middle element for the matrix

            pivotIdx = (left + right) / 2;

            pivotElement = matrix[pivotIdx /  n][pivotIdx % n];

            //return true if we find the target

            if(target == pivotElement) {

                return true;

            } else {

                //if the target is less decrease the right limit

                if(target < pivotElement) {

                    right = pivotIdx - 1;

                } 

                //else if it is greater increase the left limit

                else {

                    left = pivotIdx + 1;

                }

            }

        }

    }

}