Binary Search (AQA GCSE Computer Science): Flashcards
📚Flashcards
Practise the cards
13 cards from this deck
ShowHide
Practise the cards
13 cards from this deck
Searching algorithms
Searching algorithms
Methods computers use to find specific data or confirm absence
Two main types of searching algorithms
Two main types of searching algorithms
Linear search and binary search
How linear search works
How linear search works
Checks each item one by one from start until found or end reached
Alternative name for linear search
Alternative name for linear search
Sequential search
Binary search key requirement
Binary search key requirement
List must be sorted in order first
Binary search strategy type
Binary search strategy type
Divide and conquer
Binary search checks which value repeatedly
Binary search checks which value repeatedly
Middle value
Linear search worst case for 1 million items
Linear search worst case for 1 million items
Up to 1 million comparisons
Binary search max comparisons for 1 million items
Binary search max comparisons for 1 million items
Only 21 comparisons
Why binary search is much faster
Why binary search is much faster
Halves the remaining items with each comparison
When to use linear search
When to use linear search
Data unsorted, small datasets, or simple implementation needed
When to use binary search
When to use binary search
Data sorted/sortable, large datasets, need maximum efficiency
Binary search only works on what data type
Binary search only works on what data type
Sorted data only