title: Complexity of searching sorted matrix
body: <p>Suppose we have a matrix of size NxN of numbers where all the rows and columns are in increasing order, and we want to find if it contains a value v. One algorithm is to perform a binary search on the middle row, to find the elements closest in value to v:  M[row,col] &lt; v &lt; M[row,col+1]    (if we find v exactly, the search is complete). Since the matrix is sorted we know that v is larger than all elements in the sub-matrix M[0..row, 0..col] (the top-left quadrant of the matrix), and similarly it's smaller than all elements in the sub-matrix M[row..N-1, col+1..N-1] (the bottom right quadrant). So we can recursively search the top right quadrant M[0..row-1, col+1..N-1] and the bottom left quadrant M[row+1..N-1, 0..col]. </p>
  
  <p>The question is what is the complexity of this algorithm ?</p>
  
  <p>Example:  Suppose we have the 5x5 matrix shown below and we are searching for the number 25:</p>
  
  <pre><code>0 10 20 30 40
  1 11 21 31 41
  2 12 22 32 42
  3 13 23 33 43
  4 14 24 34 44
  </code></pre>
  
  <p>In the first iteration we perform binary search on the middle row and find the closest element which is smaller than 25 is 22 (at row=2 col=2). So now we know 25 is larger than all items in the top-left 3x3 quadrant:</p>
  
  <pre><code>0 10 20
  1 11 21
  2 12 22
  </code></pre>
  
  <p>Similary we know 25 is smaller than all elements in the bottom right 3x2 quadrant:</p>
  
  <pre><code>32 42
  33 43
  34 44
  </code></pre>
  
  <p>So, we recursively search the remaining quadrants - the top right 2x2:</p>
  
  <pre><code>30 40
  31 41
  </code></pre>
  
  <p>and the bottom left 2x3:</p>
  
  <pre><code>3 13 23
  4 14 24
  </code></pre>
  
  <p>And so on. We essentially divided the matrix into 4 quadrants (which might be of different sizes depending on the result of the binary search on the middle row), and then we recursively search two of the quadrants.</p>