| TOPIC: Linear Search | |
| DEFINITION: Linear search is a simple algorithm used to find a specific element within a list or array by checking each element one by one. It solves the problem of locating a particular item in an unsorted collection of data. This method is straightforward but can be time-consuming for large datasets. | |
| TIME_COMPLEXITY: The time complexity of linear search is O(n) in all cases (best, average, and worst), because in the worst-case scenario, the algorithm has to check every element in the list. | |
| SPACE_COMPLEXITY: The space complexity is O(1), as linear search only uses a constant amount of space to store the target element and the current index being examined. | |
| USE_WHEN: Linear search is the right tool when the dataset is small or when the data is mostly unsorted, making other search algorithms like binary search impractical. It's also useful when the cost of sorting the data outweighs the cost of performing a linear search. | |
| AVOID_WHEN: Linear search is a poor choice when dealing with large datasets, as its linear time complexity can lead to slow performance; in such cases, algorithms like binary search or hash-based searches are more efficient. | |
| EXAMPLE: | |
| Suppose we have a list [3, 1, 4, 2] and we're looking for the element 2. | |
| Start with the first element: [3, 1, 4, 2] | |
| -> Check if 3 matches 2: no, move to the next element | |
| [3, 1, 4, 2] | |
| -> Check if 1 matches 2: no, move to the next element | |
| [3, 1, 4, 2] | |
| -> Check if 4 matches 2: no, move to the next element | |
| [3, 1, 4, 2] | |
| -> Check if 2 matches 2: yes, found! | |
| Result: Element 2 found at index 3 | |
| REAL_WORLD_ANALOGY: Linear search is similar to looking for a specific book in a library by checking each shelf one by one, as opposed to using a catalog system that allows for faster lookup. | |
| SOURCE_NOTE: Concepts referenced from general knowledge of algorithms and data structures. |