A table is a list in disguise
Search a table whose rows continue from one to the next as if it were one long sorted list. About 12 minutes.
Number the cells
A table has rows and columns. Suppose each row is sorted, and the first value of every row is bigger than the last value of the row before. Read the table row by row like text, and you get one long sorted list.
Number the cells 0, 1, 2 and so on in that reading order. You can search these numbers with ordinary binary search, as long as you can turn a number back into a row and column.
rows, cols = 3, 4 last_cell = rows * cols - 1 # 11
Positions 0 to 11. The middle is position 5, which is row 1, column 1, holding 11. 3 is smaller, so look left.
Position to row and column
With c columns, cell number p lies in row p divided by c, rounded down, and column p modulo c. For example, in a table with 4 columns, cell 6 is in row 1 (6 divided by 4) and column 2 (the remainder).
Everything else is the usual search: read the middle cell, return if it matches, and keep the lower or higher half otherwise.
cell = 6 row = cell // 4 col = cell % 4 # row 1, column 2
A table has 5 columns. Which row and column is cell number 13?
- ARow 2, column 3
- BRow 3, column 2
- CRow 1, column 8
Show the answer
Row 2, column 3. 13 divided by 5 is 2 with remainder 3.
Search a sorted table
matrix is a table of whole numbers with at least one row and one column. Each row is sorted from smallest to largest, and the first number of each row is bigger than the last number of the row above. Return whether target appears in the table.
matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 3 → true
1 ≤ rows, columns ≤ 100 · −1,000,000 ≤ value ≤ 1,000,000