concept · INFO-CS-ADS-117Linear Search
Linear search is a simple searching algorithm that checks elements sequentially from the beginning of a collection until the target is found or all elements have been examined.
Explanation
Overview
Linear search, also called sequential search, is an algorithm that compares a target value with each element in a collection in sequence. It does not require the collection to be sorted.
Purpose
Its purpose is to locate a target in a collection when a straightforward search method is sufficient or when the data is not organized in a searchable order.
Working principle
The algorithm begins with the first element, compares it with the target, and proceeds to the next element whenever the current value does not match. It stops when a match is found or the collection ends.
Key concepts
name: Core idea; description: The central focus of linear search is the capability described here: Linear search is a simple searching algorithm that checks elements sequentially from the beginning of a collection until the target is found or all elements have been examined.; name: Problem context; description: Linear Search is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using linear search, check its assumptions, input requirements, expected output, and resource constraints.
Space complexity
O(1) auxiliary space for the standard iterative implementation because it uses only a small number of variables.
Example
Consider the array [12, 7, 25, 9, 18] and the target 9. Linear search compares 12, then 7, then 25, and finally 9. The target is found at index 3 after four comparisons.
Pseudocode
LINEAR_SEARCH(A, target):
for i = 0 to length(A) - 1:
if A[i] == target:
return i
return -1
Example or application
Consider the array [12, 7, 25, 9, 18] and the target 9. Linear search compares 12, then 7, then 25, and finally 9. The target is found at index 3 after four comparisons.
Definition
Linear search, also called sequential search, is an algorithm that compares a target value with each element in a collection in sequence. It does not require the collection to be sorted.
Purpose
Its purpose is to locate a target in a collection when a straightforward search method is sufficient or when the data is not organized in a searchable order.
Working Principle
The algorithm begins with the first element, compares it with the target, and proceeds to the next element whenever the current value does not match. It stops when a match is found or the collection ends.
Algorithm Steps
Start at the first element of the collection.
Compare the current element with the target value.
If they match, return the current index or element.
If they do not match, move to the next element.
Repeat the comparison until a match is found or no elements remain.
If the collection is exhausted, report that the target is absent.
Pseudocode
LINEAR_SEARCH(A, target):
for i = 0 to length(A) - 1:
if A[i] == target:
return i
return -1
Data Requirements
Linear search works with both sorted and unsorted collections. It requires only that the elements can be accessed and compared with the target.
Best Case
O(1) time. The target is found at the first position, requiring only one comparison.
Average Case
O(n) time. For a target equally likely to appear at any position in a collection of n distinct elements, a successful search requires approximately (n + 1) / 2 comparisons.
Worst Case
O(n) time. The target is at the final position or is absent, so every element must be examined.
Space Complexity
O(1) auxiliary space for the standard iterative implementation because it uses only a small number of variables.
Comparison Count
For n elements, the algorithm performs at most n element comparisons. An unsuccessful search always examines all n elements.
Duplicate Handling
The standard implementation returns the first matching occurrence because it stops immediately after finding a match. It can be modified to return the last occurrence or collect all matching positions.
Advantages
Works with unsorted data.
Very easy to understand and implement.
Requires no additional data structure.
Uses constant auxiliary space in its iterative form.
Works with arrays and sequentially accessible collections.
Limitations
Can require examining every element.
Becomes inefficient for very large collections.
Does not benefit from sorted order unless the implementation adds an early stopping condition.
Repeated searches may be expensive when the collection is large.
Optimized Variant
If the collection is sorted in ascending order, linear search can stop when the current element becomes greater than the target. This optimization is valid only when the ordering and comparison rules are consistent.
Practical Applications
Searching small lists.
Checking whether a value exists in an unsorted collection.
Finding a record in a short sequence.
Searching linked lists without an additional index.
Implementing simple lookup operations.
Implementation Considerations
The implementation should handle empty collections, missing values, duplicate values, and the collection's valid index range. In languages with zero-based indexing, the first element is at index 0.
Key Takeaway
Linear search is useful because it works without special data preparation. Its simplicity makes it suitable for small or unsorted collections, although its O(n) worst-case time can be costly for large datasets.
Key Concepts
| Name | Description |
|---|
Core idea | The central focus of linear search is the capability described here: Linear search is a simple searching algorithm that checks elements sequentially from the beginning of a collection until the target is found or all elements have been examined. |
Problem context | Linear Search is relevant when a computational task requires the behavior or capability described by this topic. |
Correct use | Before using linear search, check its assumptions, input requirements, expected output, and resource constraints. |
Practice Questions
| Question | Answer |
|---|
What is the main purpose of linear search? | Linear search is a simple searching algorithm that checks elements sequentially from the beginning of a collection until the target is found or all elements have been examined. |
What should be checked before applying linear search? | For linear search, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of linear search be validated? | Trace a representative linear search case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Learning Objectives
Explain the central idea and purpose of linear search.
Identify the assumptions, inputs, and conditions relevant to linear search.
Evaluate an application of linear search for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Scienexy Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures