Search in Sorted Grid

You're given a 2D grid of integers, grid, where each row is sorted (without duplicates), and the last value in each row is smaller than the first value in the following row. You are also given a target value, target. If the target is in the grid, return an array with its row and column indices. Otherwise, return [-1, -1].

Example 1:

  • Input: target = 4, grid = [[1, 2, 4, 5], [6, 7, 8, 9]]
  • Output: [0, 2]

Example 2:

  • Input: target = 3, grid = [[1, 2, 4, 5], [6, 7, 8, 9]]
  • Output: [-1, -1]
1def searchInSortedGrid(grid: List[List[int]], target: int) -> List[int]:
2    if not grid: return [-1, -1]
3    rows, cols = len(grid), len(grid[0])
4    l, r = 0, rows * cols - 1
5    
6    while l <= r:
7        mid = (l + r) // 2
8        row, col = mid // cols, mid % cols
9        val = grid[row][col]
10        
11        if val == target:
12            return [row, col]
13        elif val < target:
14            l = mid + 1
15        else:
16            r = mid - 1
17            
18    return [-1, -1]
Previous
Race Overtaking
Next
Search in Huge Array
1
2
4
5
6
7
8
9
l=0
r=7
mid=3
row=0
col=3
val=5
Step 1 / 4
Step 1:
Flatten grid to 1D array of size 8. l=0, r=7. mid=3.
Focus: select @ [3]
l=0r=7mid=3row=0col=3val=5