Show problems as
Classic problem #74MediumArrayBinary SearchMatrix

Search a 2D Matrix

Real-world version: Paged Offset Lookup
Tracked in this browser only
Read Search a 2D Matrix on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A calibration archive keeps signed offset readings in fixed-width pages. You are given pages, a list of m pages of n readings each, laid out so that:

  • readings grow strictly from left to right inside a page, and
  • every reading on a page is strictly smaller than every reading on the page after it.

Given an integer probe, report whether that exact reading is filed anywhere in the archive.

Return true when the archive holds probe, otherwise false. The archive can be large, so your lookup must run in time logarithmic in the total reading count m * n; walking every page is too slow.

Examples

Example 1

Input
pages = [[-9, -4, 1], [6, 11, 20]], probe = 11
Output
true

Reading 11 sits in the second slot of the second page, so the archive holds it.

Example 2

Input
pages = [[-9, -4, 1], [6, 11, 20]], probe = 5
Output
false

Nothing between 1 and 6 was ever filed, so 5 is absent even though it falls inside the archive's range.

Example 3

Input
pages = [[-10], [0], [10]], probe = 10
Output
true

Pages of a single reading are allowed; the last page carries 10.

Constraints

  • m == pages.length
  • n == pages[i].length
  • 1 <= m, n <= 100
  • -10^4 <= pages[i][j], probe <= 10^4
  • Readings ascend across the whole archive when the pages are read in order

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def locate_offset(pages: list[list[int]], probe: int) -> bool:
Java
public boolean locateOffset(int[][] pages, int probe)

More on the same topics