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
What is the Search Space Invariant in Binary Search?
After each iteration, if the target is in the array, it must lie between the pointers L and R
What is the Convergence Invariant in Binary Search?
The size of the search space decreases after each iteration, ensuring the algorithm eventually terminates.
What is the Ordering Invariant in Binary Search?
The relative order of elements in the array remains the same throughout the search — the array must be sorted and unmodified.
What if there are multiple elements with same vale and we want to return the index of the first occurrence?
What are the steps to do binary search?
- Let L be the first element of the array and R be the las element of the array.
- Calculate M = (L+R)/2
- Compare a[M] with
- Repeat step 2 and 3 until M is returned, or if L>R return -1
What is the difference in binary search in step 3 a[M] when it comes to multiple elements?
if a[M] is equal to x, record the position but keep searching to the left (R=M - 1)
What are the pros of binary search?
- Less time consuming
- Efficient for large datasets
What are the cons of binary search?
- Input must be sorted first
- Not suitable for frequently changing datasets
- Less effective on data structures that do not provide random/direct access
What is Merge Sort?
A Divide & Conquer algorithm developed by John von Neumann in 1945.
What is the main principle behind Merge Sort?
Merging two sorted lists is more efficient than sorting two unsorted lists.
What are the two key steps in Merge Sort?
1.Split the list into halves recursively.
2.Merge the sorted halves back together.
What happens in Step 1 (Split) of Merge Sort?
The array is recursively divided into two subarrays until each subarray contains only one element.
