A search algorithm that checks each element in a list one by one, starting from the first, until the target is found or the entire list has been examined. Linear search works on any list regardless of order, making it the most universally applicable search algorithm.
Definition
A search algorithm that checks each element in a list one by one, starting from the first, until the target is found or the entire list has been examined. It is the simplest search algorithm and works on both sorted and unsorted data.
💡 Intuition
Looking for your keys by checking every pocket and drawer in order.
🎯 Core Idea
Simple but slow for large lists — must check up to every element in the worst case.
Example
Formula
🌟 Why It Matters
Linear search works on any list regardless of order, making it the most universally applicable search algorithm. It serves as the baseline against which more efficient algorithms like binary search are measured.
💭 Hint When Stuck
To implement linear search, start at index 0 and compare each element to the target. If a match is found, return that index. If you reach the end without finding a match, return -1 or a 'not found' indicator. No sorting or special preparation is needed.
Formal View
Related Concepts
🚧 Common Stuck Point
Linear search works on any list; binary search is faster but requires sorted data.
⚠️ Common Mistakes
- Using linear search on large sorted datasets when binary search would be dramatically faster
- Forgetting to handle the case where the element is not found, leading to index errors
- Stopping at the first match when you need to find all occurrences of the target value
Frequently Asked Questions
What is Linear Search in CS Thinking?
A search algorithm that checks each element in a list one by one, starting from the first, until the target is found or the entire list has been examined. It is the simplest search algorithm and works on both sorted and unsorted data.
What is the Linear Search formula?
When do you use Linear Search?
To implement linear search, start at index 0 and compare each element to the target. If a match is found, return that index. If you reach the end without finding a match, return -1 or a 'not found' indicator. No sorting or special preparation is needed.
Next Steps
How Linear Search Connects to Other Ideas
To understand linear search, you should first be comfortable with searching and array. Once you have a solid grasp of linear search, you can move on to binary search and efficiency.