Week 2 - Binary Search And Merge Sort Flashcards
What are the Pros of Linear Search?
- Easy to implement
- Use less money
- No need for sorting
- Efficient for small and unsourced datasets
What are the cons of Linear Search?
- Inefficient for large datasets
- No optimisation potential
Define Binary Search
It an efficient algorithm for finding an element in a sorted array.
What an a classic example of a binary search
Divide and Conquer approach in algorithm design
What are the common design approaches?
- Brute Force ( Linear Search)
- Divide and conquer ( Binary Search, Merge Sort and QuickSort)
- Greedy (Dijkstra)
What are the 4 steps to do Binary Search?
- Let L be the first element of the array and R be the last element of the array
- Calculate M=(L+R)/2
- Compare a[M] with x
- Repeat step 2 and 3 until M is returned or if L>R, return -1
What happens when a[M] is greater or equal to x?
- When a[M] is greater than x, it means R= M-1
- When a[M] is equal to x, it means R=M-1
- Otherwise, L=M+1
Define Iterative in Space complexity
Iterative: O(1). As it uses a constant amount of space for L,R and M
Define Recursive in Space complexity
Recursive: O(log n). At each recursive call, a new layer is added to the call stack and will allocate additional memory to it.
What is the pre-conditions in a binary search?
- The input must be sorted in either ascending or descending order.
- The elements must be allow for an order relationship
- Have direct access to any elements within the input
What is the Post-conditions in a Binary search?
- If the target element is in the array, the algorithm returns the index of the element.
- Otherwise, returns -1
- The input remains unchanged
What are the three invariants found in binary search?
- Search Space invariant
- Convergence Invariant
- Ordering Invariant
