from __future__ import annotations

# This is the precision for this function which can be altered.
# It is recommended for users to keep this number greater than or equal to 10.
UpperCAmelCase_								=							10

def 							UpperCamelCase				(    lowerCAmelCase_       ,					lowerCAmelCase_       ,					lowerCAmelCase_       ,					lowerCAmelCase_   )		->						int:




       '''simple docstring'''






       for i in range(lowerCAmelCase_       ,					lowerCAmelCase_   ):
              if array[i] == target:
                     return i
       return -1

def 							UpperCamelCase				(    lowerCAmelCase_       ,					lowerCAmelCase_   )		->						int:




       '''simple docstring'''






       _A=	0
       _A=	len(lowerCAmelCase_   )
       while left <= right:
              if right - left < precision:
                     return lin_search(lowerCAmelCase_       ,					lowerCAmelCase_       ,					lowerCAmelCase_       ,					lowerCAmelCase_   )

              _A=	(left + right) // 3 + 1
              _A=	2 * (left + right) // 3 + 1

              if array[one_third] == target:
                     return one_third
              elif array[two_third] == target:
                     return two_third

              elif target < array[one_third]:
                     _A=	one_third - 1
              elif array[two_third] < target:
                     _A=	two_third + 1

              else:
                     _A=	one_third + 1
                     _A=	two_third - 1
       else:
              return -1

def 							UpperCamelCase				(    lowerCAmelCase_       ,					lowerCAmelCase_       ,					lowerCAmelCase_       ,					lowerCAmelCase_   )		->						int:




       '''simple docstring'''






       if left < right:
              if right - left < precision:
                     return lin_search(lowerCAmelCase_       ,					lowerCAmelCase_       ,					lowerCAmelCase_       ,					lowerCAmelCase_   )
              _A=	(left + right) // 3 + 1
              _A=	2 * (left + right) // 3 + 1

              if array[one_third] == target:
                     return one_third
              elif array[two_third] == target:
                     return two_third

              elif target < array[one_third]:
                     return rec_ternary_search(lowerCAmelCase_       ,					one_third - 1       ,					lowerCAmelCase_       ,					lowerCAmelCase_   )
              elif array[two_third] < target:
                     return rec_ternary_search(two_third + 1       ,					lowerCAmelCase_       ,					lowerCAmelCase_       ,					lowerCAmelCase_   )
              else:
                     return rec_ternary_search(one_third + 1       ,					two_third - 1       ,					lowerCAmelCase_       ,					lowerCAmelCase_   )
       else:
              return -1


if __name__ == "__main__":
      import doctest

      doctest.testmod()

      UpperCAmelCase_								=							input('''Enter numbers separated by comma:\n''').strip()
      UpperCAmelCase_								=							[int(item.strip()) for item in user_input.split(''',''')]
      assert collection == sorted(collection), F"List must be ordered.\n{collection}."
      UpperCAmelCase_								=							int(input('''Enter the number to be found in the list:\n''').strip())
      UpperCAmelCase_								=							ite_ternary_search(collection, target)
      UpperCAmelCase_								=							rec_ternary_search(0, len(collection) - 1, collection, target)
      if resulta != -1:
            print(F"Iterative search: {target} found at positions: {resulta}")
            print(F"Recursive search: {target} found at positions: {resulta}")
      else:
            print('''Not found''')
def 							UpperCamelCase				(    )		->						list[list[int]]:




       '''simple docstring'''






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


UpperCAmelCase_								=							generate_large_matrix()
UpperCAmelCase_								=							(
    [[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 							UpperCamelCase				(    lowerCAmelCase_   )		->						None:




       '''simple docstring'''






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

def 							UpperCamelCase				(    lowerCAmelCase_   )		->						int:




       '''simple docstring'''






       _A=	0
       _A=	len(lowerCAmelCase_   ) - 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:
              _A=	(left + right) // 2
              _A=	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:
                     _A=	mid + 1
              else:
                     _A=	mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
       return len(lowerCAmelCase_   )

def 							UpperCamelCase				(    lowerCAmelCase_   )		->						int:




       '''simple docstring'''






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

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

def 							UpperCamelCase				(    lowerCAmelCase_   )		->						int:




       '''simple docstring'''






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

def 							UpperCamelCase				(    lowerCAmelCase_   )		->						int:




       '''simple docstring'''






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

def 							UpperCamelCase				(    )		->						None:




       '''simple docstring'''






       from timeit import timeit

       print('Running benchmarks'   )
       _A=	(
           '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
       ):
              _A=	timeit(F"{func}(grid=grid)"       ,					setup=lowerCAmelCase_       ,					number=5_00   )
              print(F"{func}() took {time:0.4f} seconds"   )


if __name__ == "__main__":
      import doctest

      doctest.testmod()
      benchmark()