Start learning free

LESSON 330 OF 540 · BINARY SEARCH

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

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

    GO · BINARY SEARCH

    Search A 2d Matrix in Go, explained

    Problem overview

    The function searchMatrix receives matrix, a slice of rows where each row is a []int, and an integer target. It returns true if target appears anywhere in the matrix and false otherwise.

    The matrix is special. Every row is sorted in non-decreasing order, and each row starts with a value greater than the last value of the row before it. Take this matrix:

    1   3   5   7
10  11  16  20
23  30  34  60

    With target = 3 the answer is true (row 0, column 1). With target = 13 it is false: 13 would sit between 11 and 16 in row 1, and it isn't there. With target = 30 it is true (row 2, column 1).

    The lesson asks for O(log(m · n)) time and O(1) extra space, where m is the number of rows and n the number of columns. Checking every cell would cost O(m · n).

    Approach: one sorted list in disguise

    The two properties together mean something simple: if you read the matrix row by row, left to right, the values never go down. The example reads as 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60, one sorted list of 12 values. Binary search works on any sorted sequence, so it works here.

    The catch is that the list doesn't exist in memory; the data is a slice of slices. Building a flat copy would take O(m · n) time and space and defeat the purpose. Instead, the search works on positions from 0 to m * n - 1 and converts a position into a row and a column only when it needs to read a value.

    The conversion is plain arithmetic. Every row holds n values, so the positions before p fill p / n whole rows, and p % n more cells of the next row. That makes the row p / n and the column p % n. With 4 columns, position 9 is row 2, column 1, which is where the 30 lives. Both operations use integer division, which rounds down for non-negative numbers, so no floating point is involved.

    Step by step

    1. Measure the matrix. m is the number of rows, len(matrix), and n is the length of the first row. Every row has the same length, so the first one speaks for all of them.
    2. Set the search range to every position: left starts at 0 and right at m*n-1. Both ends are inclusive, so right is the last position itself.
    3. Loop while the range is non-empty. Go has no while; a for with only a condition does that job. The condition is left <= right, because when the two are equal one position is still unchecked.
    4. Pick the middle position as left + (right-left)/2. It rounds down, and unlike (left+right)/2 the sum can't overflow in languages with fixed-width integers. Go's int is 64 bits so the lesson's sizes are safe either way, but the habit costs nothing.
    5. Turn the position into a cell with middle/n and middle%n, and read the value there.
    6. Found it? If the value equals target, return true.
    7. Value too small? Then target can only be at a later position, so move left to middle + 1. The value at middle was already checked, so keeping it in the range would risk an endless loop.
    8. Value too big? Move right to middle - 1.
    9. Range empty? When the loop ends, every position has been ruled out, so return false.

    The solution in Go

    func searchMatrix(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])
    left, right := 0, m*n-1
    for left <= right {
        middle := left + (right-left)/2
        value := matrix[middle/n][middle%n]
        if value == target {
            return true
        } else if value < target {
            left = middle + 1
        } else {
            right = middle - 1
        }
    }
    return false
}

    A few Go details:

    • Multiple assignment with :=. m, n := len(matrix), len(matrix[0]) declares both variables in one statement, and so does left, right := 0, m*n-1. All the right-hand expressions are evaluated first.
    • A [][]int is a slice of slices. matrix[row][col] indexes the outer slice and then the row. Go checks both indexes at run time and panics when one is out of range.
    • Integer / and %. Between two ints, / drops the fraction and % gives the remainder. For the non-negative positions used here, p / n and p % n are exactly the row and column.
    • No parentheses around conditions. Go's for and if take bare conditions, and the braces are required.

    Here is the search for 30 in the example matrix, printing what each pass reads:

    left=0 right=11 middle=5 row=1 col=1 value=11
left=6 right=11 middle=8 row=2 col=0 value=23
left=9 right=11 middle=10 row=2 col=2 value=34
left=9 right=9 middle=9 row=2 col=1 value=30

    It takes four reads out of 12 cells. The last pass has left == right, which shows why the loop condition needs <=. For 13 the search reads 11, 23 and 16, then left (6) passes right (5) and the function returns false.

    Complexity

    Time: O(log(m · n)). Each pass discards at least half of the remaining positions, so the loop runs about log2(m · n) times: around 20 passes for a million cells. Each pass does a constant amount of work, because reading a cell is just two index operations.

    Space: O(1). The function keeps a handful of integers. It never builds the flat list; the cell is found by arithmetic.

    Edge cases and common mistakes

    • A single cell. For [[5]], the range is just position 0. Target 5 returns true and target 4 returns false.
    • One row or one column. [[1, 2, 3]] (m = 1) and [[1], [3], [5]] (n = 1) both work with the same code: with one column, middle/n is middle and middle%n is 0.
    • Using left < right. When one position is left, a strict comparison skips it, so a target at that position, like the 30 above, would be reported missing.
    • Setting left = middle or right = middle. The value at middle has been ruled out. Keeping it can make the range stop shrinking, and the loop never ends.
    • Swapping m and n. The row is middle / n, with n the number of columns, not rows. Dividing by m reads the wrong cells or goes out of range.
    • Targets outside the range. A target below the first value (0 in the example) or above the last one (61) simply runs the range down to empty and returns false.
    • An empty matrix. matrix[0] panics for a slice with no rows. The lesson guarantees at least one row and one column, so the solution doesn't guard against it; in code of your own, check len(matrix) == 0 first.

    Testing

    With the example matrix, the function returns these results:

    • target 3 gives true.
    • target 13 gives false.
    • target 30 gives true.
    • target 1 (the first value) gives true, and target 60 (the last) gives true.
    • target 0 and target 61 both give false.

    Other shapes: [[5]] with 5 gives true, with 4 gives false; [[1, 2, 3]] with 3 gives true; [[1], [3], [5]] with 3 gives true.

    Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free