Start learning free

LESSON 333 OF 543 · BINARY SEARCH

Search a 2D Matrix in Rust: 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
-10⁹ <= matrix[i][j], target <= 10⁹
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

Guided

Ctrl + Enter to check

RUST · BINARY SEARCH

Search A 2d Matrix in Rust, explained

Problem overview

The function search_matrix receives a Vec<Vec<i32>> named matrix and an i32 named target. It returns true if the target appears anywhere in the matrix and false otherwise. The matrix has two properties: every row is sorted, and every row starts with a value larger than the last value of the row above it.

Take this matrix:

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

Searching for 3 gives true (row 0, column 1), 13 gives false, and 30 gives true (row 2, column 1). The lesson's tests have up to a million cells, so the search has to be fast.

Approach: one sorted list in disguise

Checking every cell takes O(m · n). The two properties allow much more. If you read the rows one after another, the values never go down, so the matrix is really one sorted list of m * n values. For the example above that list is 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60.

A sorted list can be searched with binary search: look at the middle, and discard the half that cannot hold the target. That takes O(log(m · n)) steps. The matrix is never copied into a list. Instead, the search works on positions from 0 to m * n - 1, and a small piece of arithmetic turns a position into a cell. Every row holds n values, so position p is in row p / n (the number of whole rows before it) and column p % n (what is left over). With 4 columns, position 9 is row 2, column 1, which holds 30.

Step by step

Store the dimensions. m is matrix.len() and n is matrix[0].len(). Every row has the same length, so the first row tells you the number of columns. Both are converted with as i32, because len() returns a usize and Rust only does arithmetic between two numbers of the same type.
Set the search range. left starts at 0i32 and right at m * n - 1, the first and last positions. They are i32 on purpose: if right were a usize, then middle - 1 at position 0 would go below zero. An i32 simply becomes -1, which ends the loop.
Loop while left <= right. When the two are equal, one position is still unchecked, so < would miss it.
Find the middle: left + (right - left) / 2. Integer division rounds down. Adding half the distance to left gives the same position as (left + right) / 2 but the sum can never overflow.
Turn the position into a cell and read its value: row middle / n, column middle % n, each converted with as usize, because Rust indexes a vector only with a usize.
Compare. If value == target, return true.
Value too small: the target can only be at a later position, so left = middle + 1.
Value too big: right = middle - 1. In both cases the position at middle was already checked, so it leaves the range. Keeping it could make the loop run forever.
After the loop, every position has been ruled out, so the function ends with false.

Here is the search for 30 in the example matrix, printing each round:

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
found

11 and 23 are smaller than 30, so the left edge moves up. 34 is bigger, so the right edge moves down to position 9, and the last round finds 30. Searching for 13 ends differently:

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=6 right=7 middle=6 row=1 col=2 value=16
not found

After 16 is too big, right becomes 5 while left is 6, the loop ends, and the function returns false.

The solution in Rust

impl Solution {
    fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
        let m = matrix.len() as i32;
        let n = matrix[0].len() as i32;
        let mut left = 0i32;
        let mut right = m * n - 1;
        while left <= right {
            let middle = left + (right - left) / 2;
            let value = matrix[(middle / n) as usize][(middle % n) as usize];
            if value == target {
                return true;
            } else if value < target {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        false
    }
}

The Rust details worth a closer look:

Casts. as i32 and as usize are explicit because Rust never converts between integer types on its own. The casts are safe here: the constraints keep m * n at most a million, and middle is never negative inside the loop.
Two indexing steps. matrix[r][c] first picks the row (a Vec<i32>) and then the element in it. Both indexes panic if they are out of bounds, so the arithmetic has to be right.
let mut left = 0i32. The suffix i32 on the literal fixes the type. right gets i32 from m * n - 1.
The last line. false has no semicolon, so it is the function's return value when the loop finishes without an early return true.
Ownership. The function takes matrix by value and only reads it, which is fine here. It builds no second list, so no extra memory is needed.

Complexity

Time: O(log(m · n)). Each round discards at least half of the positions still in range, so the loop runs at most about log2(m · n) times: around 20 rounds for a million cells. Every round does a constant amount of work.

Space: O(1). The function keeps a handful of integers. A cell is found by arithmetic, not by building a flat list.

Edge cases and common mistakes

One cell. [[5]] with target 5 is true, and with target 4 it is false. Here left and right are both 0, so the <= comparison matters.
One row or one column. [[1, 2, 3]] with target 3 gives true, and so does [[1], [3], [5]] with target 3. The same formulas work: with one column, n is 1, so the row is middle and the column is always 0.
Targets outside the range. In the example matrix, 0 and 61 both give false, and the first and last values, 1 and 60, give true.
Swapping the row and column formulas. The row is middle / n, with n the number of columns. Dividing by the number of rows reads wrong cells, or panics on an out-of-bounds index.
Searching row by row. Looping over the rows and binary-searching each one works but costs O(m log n). Treating the matrix as one list is faster.
Using middle instead of middle + 1 or middle - 1. The range then may stop shrinking and the loop never ends.

Testing

With the example matrix, these inputs give these results:

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

Try the one-cell and one-column matrices from above in the editor too.

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

Start learning free