COMP2521 Week 1 - Linear Search

💡 The Baseline 💡 基础对照

This is the simplest search algorithm. It's often used as the "baseline" comparison ("The Bad Example" for large data). Unlike Binary Search, it does not require the array to be sorted. 这是最简单、最基础的搜索算法，也是我们用来做对比的"反面教材"（在数据量大时）。它不需要数组是排好序的。

                // Linear Search Implementation
                // Returns index if found, -1 if not
                int linearSearch(int arr[], int size, int val) {
                for (int i = 0; i < size; i++) { // Walk from start to end if (arr[i]==val) { // Check one by one return
                    i; // Found it! } } return -1; // Not found } 

💡 The Analogy 💡 生活类比

It's like looking for a book on a messy shelf. You have to pick up the first book, check it, then the second, and so on. If the book is at the end (or not there), you check every single one. 就像在一个乱序的书架上找书。你只能从第一本开始，拿起来看看是不是，不是就看下一本，直到找到为止。

📊 Characteristics 📊 特点分析

No Sorting Needed: The biggest advantage. Works on any data. 不需要排序：这是它最大的优点，给什么数组都能搜。
Efficiency O(n): Slow for large data. If you have 1 million items, you might check 1 million times. 效率 O(n)：数据大时很慢。最好情况 1 次，最坏情况 n 次（平均 n/2）。

⚔️ Linear vs Binary Search ⚔️ 线性搜索 vs 二分搜索

Feature特性	Linear Search线性搜索	Binary Search二分搜索
Pre-condition 前提条件	None (Unsorted OK) 无 (乱序也行)	Must be Sorted 必须有序
Speed 速度	Slow O(n) 慢 O(n)	Fast O(log n) 快 O(log n)
Implementation 实现难度	Simple 极简	Tricky (Boundaries) 稍难 (边界处理)
Scenario 适用场景	Small / Unsorted Data 数据少、无序数组	Large / Sorted Data 数据多、已排序数组