---

import random
import time
import math


def linear_search(arr, x):
    count = 0

    for i in range(len(arr)):
        count += 1
        if arr[i] == x:
            return i, count

    return -1, count


def binary_search(arr, x):
    left = 0
    right = len(arr) - 1
    count = 0

    while left <= right:
        mid = (left + right) // 2
        count += 1

        if arr[mid] == x:
            return mid, count
        elif arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1

    return -1, count


def jump_search(arr, x):
    n = len(arr)
    step = int(math.sqrt(n))
    left = 0
    right = step
    count = 0

    while left < n and arr[min(right, n) - 1] < x:
        count += 1
        left = right
        right += step

        if left >= n:
            return -1, count

    while left < min(right, n):
        count += 1

        if arr[left] == x:
            return left, count

        if arr[left] > x:
            return -1, count

        left += 1

    return -1, count


def interpolation_search(arr, x):
    low = 0
    high = len(arr) - 1
    count = 0

    while low <= high and arr[low] <= x <= arr[high]:
        if arr[low] == arr[high]:
            count += 1

            if arr[low] == x:
                return low, count

            return -1, count

        pos = low + (x - arr[low]) * (high - low) // (arr[high] - arr[low])

        count += 1

        if arr[pos] == x:
            return pos, count
        elif arr[pos] < x:
            low = pos + 1
        else:
            high = pos - 1

    return -1, count


arr = list(range(1, 50001))

x = 37500

algorithms = {
    "Linear": linear_search,
    "Binary": binary_search,
    "Jump": jump_search,
    "Interpolation": interpolation_search
}

print("Array size:", len(arr))
print("Search element:", x)
print()

for name, func in algorithms.items():
    index, comparisons = func(arr, x)

    print(name)
    print("Index:", index)
    print("Comparisons:", comparisons)
    print()


targets = [random.randint(1, 50000) for _ in range(1000)]

print("Performance test")
print()

for name, func in algorithms.items():
    total_time = 0
    total_comparisons = 0

    for x in targets:
        start = time.perf_counter()

        index, comparisons = func(arr, x)

        end = time.perf_counter()

        total_time += end - start
        total_comparisons += comparisons

    print(name)
    print("Average comparisons:",
          round(total_comparisons / len(targets), 2))
    print("Total time:",
          round(total_time, 6))
    print()