title: Python - time complexity of binary search algorithm in nested list
body: <p>I have a nested list of numbers, where I got n number of rows and columns and every number is increasing in every row and column. </p>
  
  <p>For example:</p>
  
  <pre><code>A = [[19, 30, 31, 45, 57],
       [25, 32, 32, 51, 69],
       [33, 35, 38, 58, 78],
       [34, 49, 67, 84, 102],
       [44, 54, 73, 90, 115]]
  </code></pre>
  
  <p>I need to use binary search to find if an element is in the list and the time complexity in the worst case of the algorithm must be O(n).</p>
  
  <p>I have this code:</p>
  
  <pre><code>def find(A, v):
      i = 0
  
      for row in A:
          num = binary_search(v, row, 0, len(row) - 1)
          if num != -1:
              return(i, num)
          i += 1
  
      return None
  
  
  def binary_search(v, row, left, right):
      if left &gt; right:
          return -1
  
      mid = (left + right) // 2
  
      if row[mid] == v:
          return mid
  
      elif row[mid] &gt; v:
          return binary_search(v, row, left, mid - 1)
  
      elif row[mid] &lt; v:
          return binary_search(v, row, mid + 1, right)
  </code></pre>
  
  <p>I think that this code has time complexity O(n log n), but I'm not really sure about that. So what is the real time complexity of this code?</p>