Binary search (Edexcel GCSE Computer Science): Flashcards
📚Flashcards
Practise the cards
14 cards from this deck
ShowHide
Practise the cards
14 cards from this deck
Type of search algorithm for sorted lists
Type of search algorithm for sorted lists
Binary search
Critical requirement for binary search to work
Critical requirement for binary search to work
List must be sorted
Strategy used by binary search
Strategy used by binary search
Divide-and-conquer
First step in binary search process
First step in binary search process
Select the median (middle item)
Action if search item < median
Action if search item < median
Discard median and everything to its right
Action if search item > median
Action if search item > median
Discard median and everything to its left
What happens when search item = median
What happens when search item = median
Item is found
Median position with odd number of items
Median position with odd number of items
Middle item
Median position with even number of items
Median position with even number of items
Round down to lower middle position
Formula for median position
Formula for median position
using integer division
Max checks for 11 items in binary search
Max checks for 11 items in binary search
3 checks
Max checks for 1000 items in binary search
Max checks for 1000 items in binary search
10 checks
What each step eliminates in binary search
What each step eliminates in binary search
Roughly half of remaining possibilities
When does binary search end
When does binary search end
When item found or no more items left to check