Search-Algorithm-Efficiency-Comparison/calculator.html at main · code-explorer-O/Search-Algorithm-Efficiency-Comparison · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Search Strategy Efficiency Calculator</title>
    <script src="https://cdn.tailwindcss.com"></script>
    <script src="https://cdn.jsdelivr.net/npm/chart.js"></script>
    <!-- Chosen Palette: Warm Neutrals -->
    <!-- Application Structure Plan: This SPA is structured as a focused calculator with a dynamic visualization. It starts with a clear header. Below that, an input section allows the user to control the array size (N) via a slider AND a numerical text input for precise entry. The core output is presented in a summary card, showing the calculated threshold for M (number of searches) that dictates the better strategy. A prominent line chart dynamically illustrates the cost curves for both "Linear Search" and "Sort + Binary Search" based on the chosen N, with the x-axis representing varying M values. This structure is chosen to provide a direct answer to the user's question ("which approach is better for which N") while simultaneously offering a visual explanation of the underlying performance trade-offs, making it intuitive and educational. -->
    <!-- Visualization & Content Choices: 1. Report Info: The threshold M > (N logN) / (N - logN). Goal: Inform & Calculate. Viz: Dynamic text in a "Threshold M" card. Interaction: The calculated M threshold updates instantly as the N slider or text input is moved. Justification: Provides the direct numerical answer. 2. Report Info: Comparing O(M*N) vs O(N*logN + M*logN) across varying M. Goal: Compare & Visualize. Viz: Interactive Line Chart (Chart.js). Interaction: The chart's data dynamically re-renders as the N slider or text input is adjusted, visually shifting the cost curves and the break-even point. Justification: A line chart is ideal for showing the relationship between M and total operations for both strategies, clearly illustrating where one becomes more efficient than the other. -->
    <!-- CONFIRMATION: NO SVG graphics used. NO Mermaid JS used. -->
    <style>
        body {
            font-family: 'Inter', sans-serif;
        }
        .chart-container {
            position: relative;
            width: 100%;
            max-width: 800px; /* Limits chart width on large screens */
            margin-left: auto;
            margin-right: auto;
            height: 350px; /* Base height for the chart */
            max-height: 450px; /* Max height to prevent excessive vertical space */
        }
        @media (min-width: 768px) {
            .chart-container {
                height: 400px;
            }
        }
    </style>
</head>
<body class="bg-gray-50 text-gray-800">

    <div class="container mx-auto p-4 md:p-8">
        <header class="text-center mb-8">
            <h1 class="text-3xl md:text-4xl font-bold text-gray-900">Search Strategy Efficiency Calculator</h1>
            <p class="text-lg text-gray-600 mt-2">Find the break-even point for multiple searches based on array size.</p>
        </header>

        <main class="bg-white rounded-lg shadow-lg p-6 md:p-8">

            <section id="input-section" class="mb-8">
                <h2 class="text-2xl font-semibold mb-4 text-gray-800">Set Array Size (N)</h2>
                <div class="flex flex-col md:flex-row items-center justify-between gap-4">
                    <label for="n-slider" class="block font-medium w-full md:w-auto mb-2 md:mb-0">Number of Elements (N): <span id="n-value" class="font-bold text-indigo-600"></span></label>
                    <input id="n-slider" type="range" min="1" max="50000" value="1" step="1" class="w-full h-2 bg-gray-200 rounded-lg appearance-none cursor-pointer flex-grow">
                    <input type="number" id="n-text-input" min="1" max="50000" value="1" class="w-24 px-3 py-1 border border-gray-300 rounded-md focus:outline-none focus:ring-2 focus:ring-indigo-500">
                </div>
                <p class="text-sm text-gray-500 mt-1">Adjust the total number of elements in your unsorted array using the slider or by typing a value.</p>
            </section>

            <section id="result-summary" class="mb-8">
                <h2 class="text-2xl font-semibold mb-4 text-gray-800">Efficiency Insights</h2>
                <div class="bg-blue-50 p-4 rounded-lg text-center">
                    <h3 class="font-semibold text-blue-800">Threshold for M (Number of Searches)</h3>
                    <p class="text-3xl font-bold text-blue-900 mt-2" id="m-threshold-display">...</p>
                    <p class="text-sm text-blue-700 mt-2" id="strategy-recommendation"></p>
                </div>
            </section>

            <section id="visualization">
                <h2 class="text-2xl font-semibold mb-4 text-gray-800">Performance Curves</h2>
                <p class="text-gray-600 mb-4">This chart shows the estimated total operations for both search strategies as `M` (number of searches) increases, for the current `N` value. The point where the "Sort + Binary Search" line drops below the "Linear Search" line indicates when it becomes more efficient.</p>
                <div class="chart-container">
                    <canvas id="comparisonChart"></canvas>
                </div>
            </section>

        </main>
    </div>

    <script>
        const nSlider = document.getElementById('n-slider');
        const nTextInput = document.getElementById('n-text-input');
        const nValueSpan = document.getElementById('n-value');
        const mThresholdDisplay = document.getElementById('m-threshold-display');
        const strategyRecommendation = document.getElementById('strategy-recommendation');
        const ctx = document.getElementById('comparisonChart').getContext('2d');
        let comparisonChart;

        function formatNumber(num) {
            if (num >= 1e9) return (num / 1e9).toFixed(2) + 'B';
            if (num >= 1e6) return (num / 1e6).toFixed(2) + 'M';
            if (num >= 1e3) return (num / 1e3).toFixed(1) + 'K';
            return num.toString();
        }

        function calculateAndDisplay() {
            let N = parseInt(nSlider.value);
            // Ensure N is within slider bounds for consistency
            const minN = parseInt(nSlider.min);
            const maxN = parseInt(nSlider.max);
            N = Math.max(minN, Math.min(N, maxN));

            nValueSpan.textContent = formatNumber(N);
            nTextInput.value = N; // Synchronize text input with slider value

            // Calculate logN, handling N=1 case where log2(1) is 0
            const logN = N > 1 ? Math.log2(N) : 0;

            let thresholdM;
            let recommendationText = '';

            // Define the highlight color class
            const highlightClass = "font-bold text-green-700"; // Changed to green-700 for highlighting

            if (N <= 1) {
                thresholdM = 0;
                recommendationText = `For <span class="${highlightClass}">M >= 1</span>, use <span class="${highlightClass}">Sort + Binary Search</span>.`;
            } else if (N - logN <= 0) {
                thresholdM = Infinity;
                recommendationText = `For <span class="${highlightClass}">N=${N}</span>, <span class="${highlightClass}">Linear Search</span> is generally better for practical M values.`;
            } else {
                thresholdM = (N * logN) / (N - logN);

                if (!isFinite(thresholdM)) {
                     mThresholdDisplay.textContent = `N is too small for a clear threshold`;
                     recommendationText = `Increase N (e.g., <span class="${highlightClass}">N > 2</span>) for a clear threshold.`
                     updateChart(N, logN, thresholdM);
                     return;
                }

                const lastValueForLinearSearch = Math.floor(thresholdM);
                const firstValueForSortBinary = lastValueForLinearSearch + 1;

                mThresholdDisplay.textContent = `M > ${thresholdM.toFixed(2)}`;
                recommendationText = `For number of searches <span class="${highlightClass}">M <= ${lastValueForLinearSearch}</span>, use <span class="${highlightClass}">Linear Search</span>.`;
                recommendationText += ` For <span class="${highlightClass}">M >= ${firstValueForSortBinary}</span>, use <span class="${highlightClass}">Sort + Binary Search</span>.`;
            }

            if (isFinite(thresholdM)) {
                mThresholdDisplay.textContent = `M > ${thresholdM.toFixed(2)}`;
            } else {
                mThresholdDisplay.textContent = `N is too small for a clear threshold`;
            }

            strategyRecommendation.innerHTML = recommendationText;
            updateChart(N, logN, thresholdM);
        }

        function updateChart(N, logN, thresholdM) {
            let mMaxForChart = Math.max(20, (isFinite(thresholdM) ? Math.ceil(thresholdM * 2) : 500));
            mMaxForChart = Math.min(mMaxForChart, 1000);

            if (N <= 1) {
                mMaxForChart = 10;
            }

            const labels = [];
            const linearData = [];
            const binaryData = [];

            const step = Math.max(1, Math.floor(mMaxForChart / 50));

            for (let m = 0; m <= mMaxForChart; m += step) {
                labels.push(m);
                linearData.push(m * N);
                binaryData.push((N * logN) + (m * logN));
            }

            if (comparisonChart) {
                comparisonChart.data.labels = labels;
                comparisonChart.data.datasets[0].data = linearData;
                comparisonChart.data.datasets[1].data = binaryData;
                comparisonChart.options.scales.x.max = mMaxForChart;
                comparisonChart.update();
            } else {
                comparisonChart = new Chart(ctx, {
                    type: 'line',
                    data: {
                        labels: labels,
                        datasets: [{
                            label: 'Multiple Linear Searches (M * N)',
                            data: linearData,
                            borderColor: 'rgb(249, 115, 22)',
                            backgroundColor: 'rgba(249, 115, 22, 0.1)',
                            fill: true,
                            tension: 0.2
                        }, {
                            label: 'Sort + Binary Searches (NlogN + MlogN)',
                            data: binaryData,
                            borderColor: 'rgb(99, 102, 241)',
                            backgroundColor: 'rgba(99, 102, 241, 0.1)',
                            fill: true,
                            tension: 0.2
                        }]
                    },
                    options: {
                        responsive: true,
                        maintainAspectRatio: false,
                        scales: {
                            y: {
                                beginAtZero: true,
                                title: {
                                    display: true,
                                    text: 'Total Operations (Estimated)'
                                },
                                ticks: {
                                    callback: function(value) {
                                        return formatNumber(value);
                                    }
                                }
                            },
                            x: {
                                title: {
                                    display: true,
                                    text: 'Number of Searches (M)'
                                },
                                max: mMaxForChart
                            }
                        },
                        plugins: {
                            tooltip: {
                                callbacks: {
                                    label: function(context) {
                                        let label = context.dataset.label || '';
                                        if (label) {
                                            label += ': ';
                                        }
                                        if (context.parsed.y !== null) {
                                            label += formatNumber(context.parsed.y);
                                        }
                                        return label;
                                    }
                                }
                            }
                        }
                    }
                });
            }
        }

        nSlider.addEventListener('input', calculateAndDisplay);
        nTextInput.addEventListener('input', () => {
            let val = parseInt(nTextInput.value);
            const minN = parseInt(nTextInput.min);
            const maxN = parseInt(nTextInput.max);

            if (isNaN(val) || val < minN) {
                val = minN;
            } else if (val > maxN) {
                val = maxN;
            }
            nSlider.value = val;
            calculateAndDisplay();
        });

        nSlider.value = 1;
        nTextInput.value = 1;
        calculateAndDisplay();
    </script>
</body>
</html>