





"""simple docstring"""






def       __lowerCamelCase    (       SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE							)		->       Optional[Any]:






       """simple docstring"""




       _UpperCAmelCase     =     0
       _UpperCAmelCase     =     len(SCREAMING_SNAKE_CASE							) - 1

       while left <= right:
              # avoid divided by 0 during interpolation
              if sorted_collection[left] == sorted_collection[right]:
                     if sorted_collection[left] == item:
                            return left
                     else:
                            return None

              _UpperCAmelCase     =     left + ((item - sorted_collection[left]) * (right - left)) // (
                  sorted_collection[right] - sorted_collection[left]
              )

              # out of range check
              if point < 0 or point >= len(SCREAMING_SNAKE_CASE							):
                     return None

              _UpperCAmelCase     =     sorted_collection[point]
              if current_item == item:
                     return point
              else:
                     if point < left:
                            _UpperCAmelCase     =     left
                            _UpperCAmelCase     =     point
                     elif point > right:
                            _UpperCAmelCase     =     right
                            _UpperCAmelCase     =     point
                     else:
                            if item < current_item:
                                   _UpperCAmelCase     =     point - 1
                            else:
                                   _UpperCAmelCase     =     point + 1
       return None

def       __lowerCamelCase    (       SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE							)		->       Union[str, Any]:






       """simple docstring"""




       if sorted_collection[left] == sorted_collection[right]:
              if sorted_collection[left] == item:
                     return left
              else:
                     return None

       _UpperCAmelCase     =     left + ((item - sorted_collection[left]) * (right - left)) // (
           sorted_collection[right] - sorted_collection[left]
       )

       # out of range check
       if point < 0 or point >= len(SCREAMING_SNAKE_CASE							):
              return None

       if sorted_collection[point] == item:
              return point
       elif point < left:
              return interpolation_search_by_recursion(SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE							)
       elif point > right:
              return interpolation_search_by_recursion(SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE							)
       else:
              if sorted_collection[point] > item:
                     return interpolation_search_by_recursion(
                         SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE,point - 1							)
              else:
                     return interpolation_search_by_recursion(
                         SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE,point + 1,SCREAMING_SNAKE_CASE							)

def       __lowerCamelCase    (       SCREAMING_SNAKE_CASE							)		->       Dict:






       """simple docstring"""




       if collection != sorted(SCREAMING_SNAKE_CASE							):
              raise ValueError('Collection must be ascending sorted'							)
       return True


if __name__ == "__main__":
    import sys
    lowerCAmelCase_			=							0
    if debug == 1:
        lowerCAmelCase_			=							[10, 30, 40, 45, 50, 66, 77, 93]
        try:
            __assert_sorted(collection)
        except ValueError:
            sys.exit('''Sequence must be ascending sorted to apply interpolation search''')
        lowerCAmelCase_			=							67

    lowerCAmelCase_			=							interpolation_search(collection, target)
    if result is not None:
        print(F'''{target} found at positions: {result}''')
    else:
        print('''Not found''')













"""simple docstring"""






def       __lowerCamelCase    (       SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE							)		->       str:






       """simple docstring"""




       if a < 0 or b < 0:
              raise ValueError('the value of both inputs must be positive'							)

       _UpperCAmelCase     =     str(bin(SCREAMING_SNAKE_CASE							)							)[2:]  # remove the leading "0b"
       _UpperCAmelCase     =     str(bin(SCREAMING_SNAKE_CASE							)							)[2:]  # remove the leading "0b"

       _UpperCAmelCase     =     max(len(SCREAMING_SNAKE_CASE							),len(SCREAMING_SNAKE_CASE							)							)

       return "0b" + "".join(
           str(int(char_a == '1' and char_b == '1'							)							)
           for char_a, char_b in zip(a_binary.zfill(SCREAMING_SNAKE_CASE							),b_binary.zfill(SCREAMING_SNAKE_CASE							)							)							)


if __name__ == "__main__":
    import doctest

    doctest.testmod()






