Searching something that is not a list

Any structure you can index in order can be binary searched, including a grid.

Why it works

Position to coordinates

Number the cells from 0 in reading order. For a grid with cols columns, position p sits at row p // cols and column p % cols.

Integer division counts how many complete rows fit before you, and the remainder is how far along the current row you are. This is the same arithmetic as the block index from Unit 1, used for the opposite purpose: there it collapsed coordinates into a region, here it expands a position into coordinates.

1grid = [2    [1, 3, 5],3    [7, 9, 11],4]5cols = len(grid[0])6 7for position in range(len(grid) * cols):8    print(position, grid[position // cols][position % cols])

With that mapping, searching the grid is the ordinary boundary loop with one substitution.

1def grid_contains(grid, target):2    if not grid or not grid[0]:3        return False4    rows, cols = len(grid), len(grid[0])5    low, high = 0, rows * cols6 7    while low < high:8        mid = low + (high - low) // 29        value = grid[mid // cols][mid % cols]10        if value >= target:11            high = mid12        else:13            low = mid + 114 15    return low < rows * cols and grid[low // cols][low % cols] == target16 17print(grid_contains([[1, 3, 5], [7, 9, 11]], 9))18print(grid_contains([[1, 3, 5], [7, 9, 11]], 4))

Quick check· 5 min

Where does position 7 sit?

A grid has 3 columns. Using reading order numbered from 0, which cell is position 7?

Row 2, column 1Row 1, column 2Row 2, column 2Row 3, column 1

Problem· 18 min

Search A 2d Matrix

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1def grid_contains(grid, target):2 if not grid or not grid[0]:3 return False4 rows, cols = len(grid), len(grid[0])5 low, high = 0, rows * cols6 7 while low < high:8 mid = low + (high - low) // 29 value = grid[mid // cols][mid % cols]10 if value >= target:11 high = mid12 else:13 low = mid + 114 15 return low < rows * cols and grid[low // cols][low % cols] == target16 17print(grid_contains([[1, 3, 5], [7, 9, 11]], 9))18print(grid_contains([[1, 3, 5], [7, 9, 11]], 4))