def f(x):
 return (x - 2)**2 + 1  # minimum is at x = 2

import numpy as np
import matplotlib.pyplot as plt

def golden_section_search(f, a, b, tol=1e-5, max_iter=100):
    phi = (np.sqrt(5) - 1) / 2  # golden ratio constant
    c = b - phi * (b - a)
    d = a + phi * (b - a)
    fc = f(c)
    fd = f(d)
    history = []
    
    for i in range(max_iter):
        history.append((a, b, c, d))
        
        if fc < fd:
            b = d
            d = c
            fd = fc
            c = b - phi * (b - a)
            fc = f(c)
        else:
            a = c
            c = d
            fc = fd
            d = a + phi * (b - a)
            fd = f(d)
            
        if abs(b - a) < tol:
            break
            
    x_min = (a + b) / 2
    return x_min, history


# Example function to minimize
def f(x):
    return (x - 2)**2 + 1  # minimum at x = 2


# Run Golden Section Search
x_min_golden, golden_hist = golden_section_search(f, 0, 5)

print("Golden Section Search:")
print("Minimum x =", x_min_golden)
print("f(x) =", f(x_min_golden))



def generate_fibonacci(n):
    fib = [1, 1]
    for _ in range(2, n):
        fib.append(fib[-1] + fib[-2])
    return fib

def fibonacci_search(f, a, b, N=20, tol=1e-5):
    fib = generate_fibonacci(N + 2)
    k = 0
    c = a + (fib[N - 2] / fib[N]) * (b - a)
    d = a + (fib[N - 1] / fib[N]) * (b - a)
    fc = f(c)
    fd = f(d)
    history = []
 
    for k in range(1, N):
        history.append((a, b, c, d))
        
        if fc < fd:
            b = d
            d = c
            fd = fc
            c = a + (fib[N - k - 2] / fib[N - k]) * (b - a)
            fc = f(c)
        else:
            a = c
            c = d
            fc = fd
            d = a + (fib[N - k - 1] / fib[N - k]) * (b - a)
            fd = f(d)
        
        if abs(b - a) < tol:
            break
 
    x_min = (a + b) / 2
    return x_min, history


# Example function to minimize
def f(x):
    return (x - 2)**2 + 1  # minimum at x = 2


# Run Fibonacci Search
x_min_fibo, fibo_hist = fibonacci_search(f, 0, 5, N=20)

print("\nFibonacci Search:")
print("Minimum x =", x_min_fibo)
print("f(x) =", f(x_min_fibo))


x_vals = np.linspace(0, 4, 400)
y_vals = f(x_vals)
plt.plot(x_vals, y_vals, label="f(x)")
plt.axvline(x_min_golden, color='orange', linestyle='--', label=f"Golden Min = 2.0000")
plt.axvline(x_min_fibo, color='green', linestyle='--', label=f"Fibo Min =  2.0000")
plt.title("Golden Section vs Fibonacci Search")
plt.xlabel("x")
plt.ylabel("f(x)")
plt.legend()
plt.grid(True)
plt.show()