---
# System prepended metadata

title: search_2d

---

search_2d
======

```python

# Given a 2d array, A, of integers which are sorted such that:
# A[i, j] < A[i + 1, j] and A[i, j] < A[i, j + 1]
# e.g. ascending down columns and along rows
# develop a function, search_2d, to return the position of a query number
# For example, in python syntax

A = [[1,  4,  7,  11],  
     [3,  6,  9,  16],
     [10, 13, 14, 17]]

assert search_2d(A, 9) == (1, 2)
assert search_2d(A, 8) is None


M = A.length  // # rows
N = A[0].length  // # columns

i_start = M/2
j_start = N/2 

//looking for x

if (A[0][0] >   x)
    // not found
if (A[M-1][N-1] < x)
    //not found
if (A[0][N-1] < x)
    // not in A[0], so look in A[1:M][0:N]
if (A[0][N-1] > x)
    //not in A[:N-1], so look in A[0:M][0:N-1]w
    
