'''simple docstring'''
def  __lowerCamelCase       (      ):


      '''simple docstring'''


      return [list(range(1000 - i							,    -1000 - i							,    -1					)					) for i in range(1000					)]


lowercase__  :      Any        =					generate_large_matrix()
lowercase__  :      int        =					(
    [[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]],
    [[3, 2], [1, 0]],
    [[7, 7, 6]],
    [[7, 7, 6], [-1, -2, -3]],
    grid,
)



def  __lowerCamelCase       (      _UpperCamelCase  :  list[list[int]]					):


      '''simple docstring'''


      assert all(row == sorted(_UpperCamelCase							,    reverse=_UpperCamelCase					) for row in grid					)
      assert all(list(_UpperCamelCase					) == sorted(_UpperCamelCase							,    reverse=_UpperCamelCase					) for col in zip(*_UpperCamelCase					)					)



def  __lowerCamelCase       (      _UpperCamelCase  :  list[int]					):


      '''simple docstring'''


      UpperCAmelCase_            =  0
      UpperCAmelCase_            =  len(_UpperCamelCase					) - 1

      # Edge cases such as no values or all numbers are negative.
      if not array or array[0] < 0:
            return 0

      while right + 1 > left:
            UpperCAmelCase_            =  (left + right) // 2
            UpperCAmelCase_            =  array[mid]

            # Num must be negative and the index must be greater than or equal to 0.
            if num < 0 and array[mid - 1] >= 0:
                  return mid

            if num >= 0:
                  UpperCAmelCase_            =  mid + 1
            else:
                  UpperCAmelCase_            =  mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
      return len(_UpperCamelCase					)



def  __lowerCamelCase       (      _UpperCamelCase  :  list[list[int]]					):


      '''simple docstring'''


      UpperCAmelCase_            =  0
      UpperCAmelCase_            =  len(grid[0]					)

      for i in range(len(_UpperCamelCase					)					):
            UpperCAmelCase_            =  find_negative_index(grid[i][:bound]					)
            total += bound
      return (len(_UpperCamelCase					) * len(grid[0]					)) - total



def  __lowerCamelCase       (      _UpperCamelCase  :  list[list[int]]					):


      '''simple docstring'''


      return len([number for row in grid for number in row if number < 0]					)



def  __lowerCamelCase       (      _UpperCamelCase  :  list[list[int]]					):


      '''simple docstring'''


      UpperCAmelCase_            =  0
      for row in grid:
            for i, number in enumerate(_UpperCamelCase					):
                  if number < 0:
                        total += len(_UpperCamelCase					) - i
                        break
      return total



def  __lowerCamelCase       (      ):


      '''simple docstring'''


      from timeit import timeit

      print('''Running benchmarks'''					)
      UpperCAmelCase_            =  (
          """from __main__ import count_negatives_binary_search, """
          """count_negatives_brute_force, count_negatives_brute_force_with_break, grid"""
      )
      for func in (
          "count_negatives_binary_search",  # took 0.7727 seconds
          "count_negatives_brute_force_with_break",  # took 4.6505 seconds
          "count_negatives_brute_force",  # took 12.8160 seconds
      ):
            UpperCAmelCase_            =  timeit(F"""{func}(grid=grid)"""							,    setup=_UpperCamelCase							,    number=500					)
            print(F"""{func}() took {time:0.4f} seconds"""					)


if __name__ == "__main__":
 import doctest

 doctest.testmod()
 benchmark()






'''simple docstring'''
from collections.abc import Callable



def  __lowerCamelCase       (      _UpperCamelCase  :  Callable[[float], float]							,    _UpperCamelCase  :  float							,    _UpperCamelCase  :  float					):


      '''simple docstring'''


      UpperCAmelCase_            =  a
      UpperCAmelCase_            =  b
      if function(_UpperCamelCase					) == 0:  # one of the a or b is a root for the function
            return a
      elif function(_UpperCamelCase					) == 0:
            return b
      elif (
          function(_UpperCamelCase					) * function(_UpperCamelCase					) > 0
      ):  # if none of these are root and they are both positive or negative,
            # then this algorithm can't find the root
            raise ValueError('''could not find root in given interval.'''					)
      else:
            UpperCAmelCase_            =  start + (end - start) / 2.0
            while abs(start - mid					) > 10**-7:  # until precisely equals to 10^-7
                  if function(_UpperCamelCase					) == 0:
                        return mid
                  elif function(_UpperCamelCase					) * function(_UpperCamelCase					) < 0:
                        UpperCAmelCase_            =  mid
                  else:
                        UpperCAmelCase_            =  mid
                  UpperCAmelCase_            =  start + (end - start) / 2.0
            return mid



def  __lowerCamelCase       (      _UpperCamelCase  :  float					):


      '''simple docstring'''


      return x**3 - 2 * x - 5


if __name__ == "__main__":
      print(bisection(f, 1, 1000))

      import doctest

      doctest.testmod()





