search.linear #1
Description
Implement Linear Search Algorithm
Description
Implement the linear() method in the Search class (search.py). This method should use the linear search algorithm to find an element in a list based on a custom comparator function.
Requirements
Method Signature:
@staticmethod
def linear(data: List[Any], target: Any, comparator: Callable[[Any, Any], bool]) -> AnyParameters:
data: A list of elements to search throughtarget: The element to findcomparator: A function that takes two elements and returnsTrueif they match
Returns:
- The index of the found element
Raises:
NotFoundErrorif the target is not found in the list
Algorithm Details
Linear search works by:
- Iterating through each element in the list
- Using the comparator to check if the current element matches the target
- Returning the index immediately when found
- Raising
NotFoundErrorif the entire list is searched without finding the target
Time Complexity:
- Best case: O(1) - element is first
- Average: O(n/2)
- Worst case: O(n) - element is last or not present
Space Complexity: O(1)
Performance Requirements
Your implementation must pass the performance test with the following criteria:
- Dataset size: 100,000 elements
- Target position: Last element (worst case)
- Maximum time: 1 second
- Should efficiently iterate through large lists
Implementation Guidelines
- Use enumeration to track both index and value
- Use the comparator to check for matches (don't assume
==) - Return the first match - if duplicates exist, return the first occurrence
- Raise NotFoundError with a descriptive message when not found
- Handle edge cases:
- Empty lists (should raise NotFoundError)
- Single-element lists
- Element not in list
- Duplicate elements (return first occurrence)
- Custom comparators (not just equality)
Testing
Run the test suite to verify your implementation:
python3 -m colorful_test test_search.pyAll tests related to linear() must pass, including:
- Finding elements at various positions (first, middle, last)
- Handling different data types (integers, floats, strings, objects)
- Raising NotFoundError when appropriate
- Working with custom comparators
- Performance test with a large dataset
Example Usage
from search import Search, NotFoundError
# Basic search
data = [5, 3, 8, 1, 9, 2]
index = Search.linear(data, 8, lambda a, b: a == b)
print(index) # 2
# String search
words = ['apple', 'banana', 'cherry']
index = Search.linear(words, 'banana', lambda a, b: a == b)
print(index) # 1
# Not found
try:
Search.linear(data, 10, lambda a, b: a == b)
except NotFoundError as e:
print(e) # 10 was not foundError Handling
The NotFoundError exception is already defined in search.py. Your implementation should:
raise NotFoundError(f"{target} was not found")Acceptance Criteria
- Method correctly finds elements using linear search
- Returns the correct index of found elements
- Returns first occurrence when duplicates exist
- Raises NotFoundError when element not found
- All edge cases are handled
- Performance test completes within 1 second for 100,000 elements
- Code is clean and well-commented
Resources
Note: Do not modify the test files. Ensure your implementation passes all existing tests.