Implement Binary Search Algorithm
Description
Implement the binary() method in the Search class (search.py). This method should use the binary search algorithm to find an element in a sorted list based on a custom comparator function.
Requirements
Method Signature:
@staticmethod
def binary(data: List[Any], target: Any, comparator: Callable[[Any, Any], int]) -> Any
Parameters:
data: A sorted list of elements to search throughtarget: The element to findcomparator: A function that takes two elements and returns:
0 if elements are equal- Negative value if first element is less than second
- Positive value if first element is greater than second
Returns:
- The index of the found element, OR
NotFoundError object (not raised, just returned) if not found
Note: The current implementation has a bug - it returns NotFoundError(...) instead of raising it. Your implementation should match this behaviour for the tests to pass.
Algorithm Details
Binary search works by:
- Starting with the entire sorted list
- Comparing the middle element with the target
- If equal, return the index
- If target is smaller, search the left half
- If target is larger, search the right half
- Repeat until found or search space is empty
Time Complexity:
- Best case: O(1) - element is in the middle
- Average/Worst case: O(log n)
Space Complexity: O(1) - iterative approach
Important: Binary search only works on sorted lists!
Performance Requirements
Your implementation must pass the performance test with the following criteria:
- Dataset size: 1,000,000 elements (sorted)
- Target position: Last element (worst case)
- Maximum time: 0.01 seconds (10 milliseconds)
- Binary search should be significantly faster than linear search on large datasets
Implementation Guidelines
- Use left and right pointers to track the search space
- Calculate mid point as
(left + right) // 2
- Use the comparator to determine which direction to search
- Return NotFoundError object (not raise) when not found - this matches the existing bug
- Handle edge cases:
- Empty lists
- Single-element lists
- Element not in list
- Element smaller than all elements
- Element larger than all elements
- Negative numbers
- Floats
Testing
Run the test suite to verify your implementation:
python3 -m colorful_test test_search.py
All tests related to binary() must pass, including:
- Finding elements at various positions (first, middle, last)
- Handling different data types (integers, floats, strings with a custom comparator)
- Returning NotFoundError object when appropriate
- Performance test with a huge dataset
Example Usage
from search import Search, NotFoundError
# Basic search (sorted list required!)
data = [1, 3, 5, 7, 9, 11, 13]
index = Search.binary(data, 7, lambda a, b: a - b)
print(index) # 3
# String search with custom comparator
words = ['apple', 'banana', 'cherry', 'date']
def string_cmp(a, b):
if a < b: return -1
if a > b: return 1
return 0
index = Search.binary(words, 'cherry', string_cmp)
print(index) # 2Comparator Function
The comparator should work like this:
def number_comparator(a, b):
return a - b # Negative if a < b, 0 if equal, positive if a > bAcceptance Criteria
Resources
Note: Do not modify the test files. Please make sure your implementation passes all existing tests. Yes, the return vs raise behaviour is unusual, but it's how the tests expect it to work!
Implement Binary Search Algorithm
Description
Implement the
binary()method in theSearchclass (search.py). This method should use the binary search algorithm to find an element in a sorted list based on a custom comparator function.Requirements
Method Signature:
Parameters:
data: A sorted list of elements to search throughtarget: The element to findcomparator: A function that takes two elements and returns:0if elements are equalReturns:
NotFoundErrorobject (not raised, just returned) if not foundNote: The current implementation has a bug - it returns
NotFoundError(...)instead of raising it. Your implementation should match this behaviour for the tests to pass.Algorithm Details
Binary search works by:
Time Complexity:
Space Complexity: O(1) - iterative approach
Important: Binary search only works on sorted lists!
Performance Requirements
Your implementation must pass the performance test with the following criteria:
Implementation Guidelines
(left + right) // 2Testing
Run the test suite to verify your implementation:
All tests related to
binary()must pass, including:Example Usage
Comparator Function
The comparator should work like this:
Acceptance Criteria
Resources
Note: Do not modify the test files. Please make sure your implementation passes all existing tests. Yes, the return vs raise behaviour is unusual, but it's how the tests expect it to work!