import time
import math
import pandas as pd

# --- Search algorithms ---
def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    while left <= right:
        middle = (left + right) // 2
        if target == arr[middle]:
            return middle
        elif target < arr[middle]:
            right = middle - 1
        else:
            left = middle + 1
    return -1

def jump_search(arr, target):
    n = len(arr)
    step = int(math.sqrt(n))
    prev = 0
    while prev < n and arr[min(step, n)-1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1
    while prev < min(step, n) and arr[prev] < target:
        prev += 1
        if prev == n:
            return -1
    if prev < n and arr[prev] == target:
        return prev
    return -1

# --- Benchmark ---
def benchmark(func, arr, target, repeats=100):
    total = 0
    for _ in range(repeats):
        start = time.perf_counter()
        func(arr, target)
        total += time.perf_counter() - start
    avg_time = (total / repeats) * 1000  # Til millisekunder
    return avg_time

# --- Benchmarking ---
sizes = [1,10,11,120,121,5000,10000,100000]
data = []

for size in sizes:
    arr = list(range(size))  # Sorted array
    target = size * 3 + 1  # Not in array

    for name, func in [
        ("Lineær Søgning", linear_search),
        ("Binær Søgning", binary_search),
        ("Jump-Søgning", jump_search),
    ]:
        runtime = benchmark(func, arr, target)
        data.append({
            "Søgealgoritme": name,
            "Inputmængde (n)": size,
            "Køretid (ms)": runtime,
        })

df = pd.DataFrame(data)
df.to_csv("sorteret_algoritmetest.csv", index=False)