Binary Search (OCR A-Level Computer Science): Flashcards
📚Flashcards
Practise the cards
12 cards from this deck
ShowHide
Practise the cards
12 cards from this deck
Binary Search definition
Binary Search definition
Efficient algorithm to find target position in sorted dataset
Pre-condition for Binary Search
Pre-condition for Binary Search
Data must be sorted
Binary Search best case time complexity
Binary Search best case time complexity
- target is middle element
Binary Search worst case time complexity
Binary Search worst case time complexity
- halves search space each step
Binary Search iterative space complexity
Binary Search iterative space complexity
Binary Search recursive space complexity
Binary Search recursive space complexity
due to call stack
Action when target < middle in Binary Search
Action when target < middle in Binary Search
Search left half
Action when target > middle in Binary Search
Action when target > middle in Binary Search
Search right half
Binary Search vs Linear Search for large datasets
Binary Search vs Linear Search for large datasets
Binary Search is much faster
Why Binary Search fails on unsorted data
Why Binary Search fails on unsorted data
Only works on sorted data, gives incorrect results
Recursive Binary Search base condition
Recursive Binary Search base condition
Return -1 when low > high (target not found)
How Binary Search reduces search space
How Binary Search reduces search space
Divides search interval in half each iteration