Deebiga21/Search-algorithm-analyzer

1import streamlit as st
2import time
3import random
4
5def interpolation_search(arr, target):
6    low, high = 0, len(arr)-1
7    comparisons = 0
8
9    while low <= high and target >= arr[low] and target <= arr[high]:
10
11        comparisons += 1
12
13        if low == high:
14            if arr[low] == target:
15                return low, comparisons
16            return -1, comparisons
17
18        pos = low + ((high-low)*(target-arr[low])) // (arr[high]-arr[low])
19
20        if arr[pos] == target:
21            return pos, comparisons
22
23        if arr[pos] < target:
24            low = pos+1
25        else:
26            high = pos-1
27
28    return -1, comparisons
29
30
31def binary_search(arr,target):
32    low, high = 0,len(arr)-1
33    comparisons=0
34
35    while low <= high:
36        mid=(low+high)//2
37        comparisons+=1
38
39        if arr[mid]==target:
40            return mid,comparisons
41
42        elif arr[mid]<target:
43            low=mid+1
44
45        else:
46            high=mid-1
47
48    return -1,comparisons
49
50
51
52def performance_analysis():
53
54    sizes=[1000,5000,10000,50000,100000]
55
56    print(f"{'Size':<10}{'Interpolation':<20}{'Binary':<20}{'IS Comp':<15}{'BS Comp'}")
57    print("-"*75)
58
59
60    for size in sizes:
61
62        arr=sorted(random.sample(range(size*10),size))
63        target=random.choice(arr)
64
65
66        start=time.perf_counter()
67
68        for _ in range(100):
69            idx_is,comp_is=interpolation_search(arr,target)
70
71        is_time=(time.perf_counter()-start)/100
72
73
74
75        start=time.perf_counter()
76
77        for _ in range(100):
78            idx_bs,comp_bs=binary_search(arr,target)
79
80        bs_time=(time.perf_counter()-start)/100
81
82
83        print(f"{size:<10}{is_time:.6f}s          {bs_time:.6f}s          {comp_is:<15}{comp_bs}")
84
85
86
87arr=[2,5,10,15,23,35,48,60,75,90,105,120]
88
89target=35
90
91idx,comparisons=interpolation_search(arr,target)
92
93print("Array:",arr)
94print("Target:",target)
95print(f"Interpolation Search: Index={idx}, Comparisons={comparisons}")
96
97
98performance_analysis()