Search Algorithms Flashcards
Linear Search
Checks each element in the list sequentially until it finds the target value or reaches the end of the list
Time Complexity Linear Search
Best: O(1) - if target is in first position
AVG: O(n)
Worst: O(n)
Space Complexity Linear Search
Always: O(1)
When to use Linear Search
List is small or unsorted
When not to use Linear Search
For large datasets or if speed is important
Strengths Linear Search
Simple to implement and works on unsorted data
Weaknesses Linear Search
Inefficient for large datasets (O(n) time)
Binary Search
Binary Search requires a sorted list. It repeatedly divides the list in half, comparing the middle element to the target. If the target is smaller or larger than the middle, it continues searching in the respective half
Binary Search Time Complexity
Best: O(1)
AVG: O(log n)
Worst: O(log n)
Binary Search Space Complexity
Iterative Version: O(1)
Recursive Version: O(log n)
When to use Binary Search
When the list is sorted and you need efficient search
When not to use Binary Search
On unsorted data
Strengths of Binary Search
Very efficient for large, sorted datasets, O(log n)
Weaknesses of Binary Search
Only works on sorted data and requires extra time for sorting
When is it worth sorting first for a large dataset before using search function?
It’s worth sorting first if the dataset is going to be repeatedly searched for values.
If you only search once, just use Linear Search. It is time complexity O(n), while sorting first and then binary is O(n log n) * O(log n)
