Search-Algorithm-Efficiency-Comparison/analyzer.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
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Interactive Search Strategy Analyzer</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: The SPA is designed as an interactive dashboard. The core idea is to let the user manipulate the two key variables, N (array size) and M (number of searches), and instantly see the performance implications. The structure includes: 1. A header for context. 2. An interactive controls section with sliders for N and M for hands-on exploration, now including numerical input fields for precise control and error validation. The input fields are arranged in separate rows for better clarity. 3. A dynamic results section with summary cards showing the calculated complexities and the break-even point for M. 4. A central, dynamic line chart that visually plots the total operations for both strategies, making the comparison intuitive. This dashboard approach was chosen over a linear report structure because it transforms a static analysis into an engaging, explorable tool, which is far more effective for learning and future reference. -->
    <!-- Visualization & Content Choices: 1. Report Info: Comparing O(M*N) vs O(N*logN + M*logN). Goal: Compare. Viz: Interactive Line Chart (Chart.js). Interaction: Sliders and numerical inputs for N and M update the chart data, showing how the lines intersect and which method is more efficient under different conditions. Justification: A line chart is the best way to visually represent the crossover point of two functions. 2. Report Info: The formula M > (N*logN)/(N-logN). Goal: Inform & Calculate. Viz: Dynamic text in a "Key Takeaway" card. Interaction: The calculated threshold for M updates instantly as the N slider/input is moved. Justification: This provides an immediate, quantitative answer based on the user's input, directly connecting the interactive input to the mathematical conclusion. 3. Report Info: Total complexity values for both cases. Goal: Inform. Viz: Two summary cards. Interaction: Values update as both N and M sliders/inputs are moved. Justification: Clear, side-by-side presentation of the quantitative results for the currently selected parameters. -->
    <!-- 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;
            margin-left: auto;
            margin-right: auto;
            height: 300px;
            max-height: 400px;
        }
        @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 Analyzer</h1>
            <p class="text-lg text-gray-600 mt-2">When is it better to sort an array once, then use Binary Search?</p>
        </header>

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

            <section id="interactive-controls" class="mb-8">
                <h2 class="text-2xl font-semibold mb-4 text-gray-800">Interactive Controls</h2>
                <div class="flex flex-col gap-8"> <!-- Changed from grid to flex-col for stacking -->
                    <div>
                        <label for="n-slider" class="block font-medium mb-2">Array Size (N): <span id="n-value" class="font-bold text-indigo-600"></span></label>
                        <div class="flex items-center gap-4">
                            <input id="n-slider" type="range" min="1" max="1000000" 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="1000000" value="1" class="w-28 px-3 py-1 border border-gray-300 rounded-md focus:outline-none focus:ring-2 focus:ring-indigo-500 text-right">
                        </div>
                        <p id="n-error" class="text-red-500 text-sm mt-1 h-4"></p> <!-- Error message for N -->
                        <p class="text-sm text-gray-500 mt-1">Adjust the total number of elements in the array.</p>
                    </div>
                    <div>
                        <label for="m-slider" class="block font-medium mb-2">Number of Searches (M): <span id="m-value" class="font-bold text-indigo-600"></span></label>
                        <div class="flex items-center gap-4">
                            <input id="m-slider" type="range" min="1" max="1000" value="1" step="1" class="w-full h-2 bg-gray-200 rounded-lg appearance-none cursor-pointer flex-grow">
                            <input type="number" id="m-text-input" min="1" max="1000" value="1" class="w-28 px-3 py-1 border border-gray-300 rounded-md focus:outline-none focus:ring-2 focus:ring-indigo-500 text-right">
                        </div>
                        <p id="m-error" class="text-red-500 text-sm mt-1 h-4"></p> <!-- Error message for M -->
                        <p class="text-sm text-gray-500 mt-1">Adjust how many times you will search the array.</p>
                    </div>
                </div>
            </section>

            <section id="results" class="mb-8">
                 <h2 class="text-2xl font-semibold mb-4 text-gray-800">Analysis & Results</h2>
                 <div class="grid md:grid-cols-3 gap-4 text-center">
                    <div class="bg-orange-100 p-4 rounded-lg">
                        <h3 class="font-semibold text-orange-800">Multiple Linear Searches</h3>
                        <p class="text-2xl font-bold text-orange-900 mt-2" id="linear-cost">0</p>
                        <p class="text-sm text-orange-700">Total Operations (M * N)</p>
                    </div>
                    <div class="bg-indigo-100 p-4 rounded-lg">
                        <h3 class="font-semibold text-indigo-800">Sort + Binary Searches</h3>
                        <p class="text-2xl font-bold text-indigo-900 mt-2" id="binary-cost">0</p>
                        <p class="text-sm text-indigo-700">Total Operations (N logN + M logN)</p>
                    </div>
                    <div id="takeaway-card" class="bg-green-100 p-4 rounded-lg">
                        <h3 class="font-semibold text-green-800">Key Takeaway</h3>
                        <p class="text-lg font-bold text-green-900 mt-2" id="conclusion">Adjust sliders to see the result.</p>
                        <p class="text-sm text-green-700" id="threshold-info">Break-even point for M</p>
                    </div>
                 </div>
            </section>

            <section id="visualization">
                 <h2 class="text-2xl font-semibold mb-4 text-gray-800">Performance Comparison</h2>
                 <p class="text-gray-600 mb-4">This chart visualizes the total estimated operations for each search strategy as the number of searches (M) increases, based on the currently selected array size (N). The point where the lines cross is the "break-even" point, where the Sort + Binary Search approach 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 mSlider = document.getElementById('m-slider');
        const mTextInput = document.getElementById('m-text-input');
        const nValueSpan = document.getElementById('n-value');
        const mValueSpan = document.getElementById('m-value');

        const linearCostEl = document.getElementById('linear-cost');
        const binaryCostEl = document.getElementById('binary-cost');
        const conclusionEl = document.getElementById('conclusion');
        const thresholdInfoEl = document.getElementById('threshold-info');
        const takeawayCard = document.getElementById('takeaway-card');
        const nErrorEl = document.getElementById('n-error'); // N error message element
        const mErrorEl = document.getElementById('m-error'); // M error message element

        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 calculateCosts() {
            const N = parseInt(nSlider.value); // Always read from slider (which is synchronized with text input)
            const M = parseInt(mSlider.value); // Always read from slider (which is synchronized with text input)

            nValueSpan.textContent = formatNumber(N);
            mValueSpan.textContent = M;

            const logN = (N > 1) ? Math.log2(N) : 0; // log2(1) is 0

            const linearTotalCost = M * N;
            const binaryTotalCost = (N * logN) + (M * logN);

            linearCostEl.textContent = formatNumber(linearTotalCost);
            binaryCostEl.textContent = formatNumber(binaryTotalCost);

            const thresholdM = (N * logN) / (N - logN);

            if (linearTotalCost < binaryTotalCost) {
                conclusionEl.textContent = "Linear Search is faster.";
                takeawayCard.classList.remove('bg-indigo-100', 'border-indigo-500');
                takeawayCard.classList.add('bg-orange-100', 'border-orange-500');

            } else {
                conclusionEl.textContent = "Sort + Binary Search is faster.";
                takeawayCard.classList.remove('bg-orange-100', 'border-orange-500');
                takeawayCard.classList.add('bg-indigo-100', 'border-indigo-500');
            }

            if (N > 2) {
                thresholdInfoEl.textContent = `Use Sort+Binary if M > ${Math.ceil(thresholdM)}`;
            } else if (N === 1) { // Specific case for N=1
                 thresholdInfoEl.textContent = `For N=1, Sort+Binary is always better for M>=1.`;
            } else { // N=2 or very small N where N-logN is problematic
                 thresholdInfoEl.textContent = `N is too small for a meaningful comparison.`;
            }

            updateChart(N, logN);
        }

        function updateChart(N, logN) {
            const mMax = parseInt(mSlider.max); // Max M for chart based on slider max
            const labels = [];
            const linearData = [];
            const binaryData = [];

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

            for (let m = 0; m <= mMax; 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.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.1
                        }, {
                            label: 'Sort + Binary Searches (NlogN + MlogN)',
                            data: binaryData,
                            borderColor: 'rgb(99, 102, 241)',
                            backgroundColor: 'rgba(99, 102, 241, 0.1)',
                            fill: true,
                            tension: 0.1
                        }]
                    },
                    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)'
                                }
                            }
                        },
                        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;
                                    }
                                }
                            }
                        }
                    }
                });
            }
        }

        // Event Listeners for N slider and text input
        nSlider.addEventListener('input', () => {
            nErrorEl.textContent = ''; // Clear error on slider input
            nTextInput.value = nSlider.value; // Sync slider to text input
            calculateCosts();
        });
        nTextInput.addEventListener('input', () => {
            let val = parseInt(nTextInput.value);
            const minN = parseInt(nTextInput.min);
            const maxN = parseInt(nTextInput.max);

            if (isNaN(val) || val < minN || val > maxN) {
                nErrorEl.textContent = `Value must be between ${formatNumber(minN)} and ${formatNumber(maxN)}.`;
                return; // Stop further processing if invalid
            } else {
                nErrorEl.textContent = ''; // Clear error if valid
            }
            nSlider.value = val; // Sync text input to slider
            calculateCosts();
        });

        // Event Listeners for M slider and text input
        mSlider.addEventListener('input', () => {
            mErrorEl.textContent = ''; // Clear error on slider input
            mTextInput.value = mSlider.value; // Sync slider to text input
            calculateCosts();
        });
        mTextInput.addEventListener('input', () => {
            let val = parseInt(mTextInput.value);
            const minM = parseInt(mTextInput.min);
            const maxM = parseInt(mTextInput.max);

            if (isNaN(val) || val < minM || val > maxM) {
                mErrorEl.textContent = `Value must be between ${formatNumber(minM)} and ${formatNumber(maxM)}.`;
                return; // Stop further processing if invalid
            } else {
                mErrorEl.textContent = ''; // Clear error if valid
            }
            mSlider.value = val; // Sync text input to slider
            calculateCosts();
        });

        // Initial calculation with default values
        nSlider.value = 1000;
        mSlider.value = 150;
        calculateCosts();
    </script>
</body>
</html>