Start learning free

LESSON 329 OF 539 · BINARY SEARCH

Search a 2D Matrix in C#: Binary Search in O(log(m·n))

Practice O(log(m · n)) Read the full explanation

You are given a matrix of integers matrix with m rows and n columns, and an integer target. The matrix has two properties:

  • Each row is sorted in non-decreasing order.
  • The first value of each row is greater than the last value of the row before it.

Return true if target is in matrix, or false otherwise.

The matrix is an array of rows, and each row is an array of integers. Rows are numbered from 0, top to bottom, and columns from 0, left to right.

 

Example 1:

Input: matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
], target = 3
Output: true
Explanation: 3 is in row 0, column 1.

Example 2:

Input: matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
], target = 13
Output: false
Explanation: 13 would sit between 11 and 16 in row 1, but it isn't there.

Example 3:

Input: matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
], target = 30
Output: true
Explanation: Read row by row, the 12 values form one sorted list:
1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60.
30 is at position 9 of that list (counting from 0), which is row 2, column 1.

 

Constraints:

  • 1 <= m, n <= 1000
  • -109 <= matrix[i][j], target <= 109
  • Every row has n values, sorted in non-decreasing order, and each row starts with a value greater than the last value of the row before it.

Note:

Your algorithm should run in O(log(m · n)) time and use O(1) extra space. Checking every cell would take O(m · n).

STEP 1 OF 9
    Ctrl + Enter to check

    C# · BINARY SEARCH

    Search A 2d Matrix in C#, explained

    Problem overview

    The method SearchMatrix receives a matrix of integers, written as an int[][] (an array of rows, each row an array of int), and a target. It returns true when the target is somewhere in the matrix and false otherwise.

    The matrix has two properties: every row is sorted in non-decreasing order, and the first value of each row is greater than the last value of the row above. In the example, the matrix is {1,3,5,7}, {10,11,16,20}, {23,30,34,60}. Target 3 gives true, target 13 gives false (it would sit between 11 and 16, but isn't there) and target 30 gives true.

    The lesson asks for O(log(m · n)) time and O(1) extra space, so looking at every cell is too slow.

    Approach: one sorted list in disguise

    Read the rows one after another and the matrix becomes a single sorted list of m * n values: 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60. The second property is what makes this true, because each row starts above where the previous one ends. Binary search works on any sorted sequence, so it works here.

    The catch is that the list doesn't exist in memory. The values live in rows, and building a flat copy would cost O(m · n) space. The fix is to binary search over positions 0 to m * n - 1 and translate a position into a cell only when you need its value. With n columns, position p is in row p / n (the number of whole rows before it) and column p % n (the cells left over in its own row). With 4 columns, position 9 is row 2, column 1, which holds 30.

    Searching for 13, the loop looks at position 5 (value 11, too small, so move right), then position 8 (value 23, too big, so move left), then position 6 (value 16, too big). The range is now empty, so the answer is false.

    Step by step

    1. Read the sizes. m is matrix.Length, the number of rows, and n is matrix[0].Length, the length of the first row. Every row has the same length, so the first row speaks for all of them.
    2. Set the search range to the positions of the flat list: left = 0 and right = m * n - 1. Both ends are inclusive, so right is the last position itself.
    3. Loop while left <= right. When the two are equal, one position is still unchecked, so the condition needs <=.
    4. Pick the middle: left + (right - left) / 2. Integer division rounds down, and adding half the distance to left gives the same position as (left + right) / 2 without the risk of the sum overflowing.
    5. Convert the position to a cell with middle / n and middle % n, and read the value there.
    6. Compare. If the value equals the target, return true. If it is smaller, the target can only be at a later position, so left = middle + 1. Otherwise it is bigger, so right = middle - 1. The + 1 and - 1 matter: middle was already checked, and keeping it in the range could loop forever.
    7. Return false after the loop. Reaching that line means every position that could hold the target was ruled out.

    The solution in C#

    class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        int m = matrix.Length, n = matrix[0].Length;
        int left = 0, right = m * n - 1;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            int value = matrix[middle / n][middle % n];
            if (value == target) {
                return true;
            } else if (value < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return false;
    }
}

    The C# details worth knowing:

    • Jagged, not rectangular. int[][] is an array of arrays, indexed matrix[row][column]. A rectangular array int[,] is indexed matrix[row, column] and reports its sizes with GetLength(0) and GetLength(1). Here matrix.Length counts rows and matrix[0].Length counts columns.
    • Integer division and remainder. / on two ints drops the fraction, which is what turns a position into a row number. % gives the remainder, which is the column.
    • Overflow wraps silently. Without a checked context, int arithmetic that goes past 2147483647 wraps around. With left = 2000000000 and right = 2100000000, (left + right) / 2 gives -97483648, while left + (right - left) / 2 gives 2050000000. For this lesson m * n is at most a million, so either form is safe, but the habit costs nothing.
    • The method is a pure lookup. It reads the matrix and never changes it.

    Complexity

    Time: O(log(m · n)). Each pass of the loop halves the number of positions still possible, so the loop runs about log2(m · n) times: around 20 for a million cells. Converting a position to a cell is a division and a remainder, which take constant time.

    Space: O(1). The method keeps a handful of int variables. It never builds the flat list, because the cell is found by arithmetic.

    Searching row by row would take O(m · n). Binary searching first for the row and then inside it is also O(log m + log n), which is the same as O(log(m · n)). The single search over positions needs only one loop.

    Edge cases and common mistakes

    • One cell. {{5}} with target 5 gives true, and with target 4 gives false. The loop runs once, which is why the condition is <=.
    • One column. {{1},{3},{5}} with target 3 gives true. Here n is 1, so middle / n is the position itself and middle % n is always 0.
    • Targets outside the range. The smallest value (1) and the largest (60) are found, while 0 and 61 give false without any out-of-range access.
    • Swapping the row and column formulas. Using middle % n for the row and middle / n for the column reads the wrong cell, or goes past the end of an array and throws IndexOutOfRangeException.
    • Dividing by m instead of n. The divisor is the row length, the number of columns, not the number of rows.
    • Using middle instead of middle + 1 or middle - 1. The range then never shrinks in some cases, and the loop runs forever.

    Testing

    With the matrix {1,3,5,7}, {10,11,16,20}, {23,30,34,60}:

    • target 3 gives true, target 13 gives false, target 30 gives true.
    • target 1 gives true, target 60 gives true, target 0 gives false, target 61 gives false.
    • {{5}} with 5 gives true; with 4 gives false.
    • {{1},{3},{5}} with 3 gives true.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free