Binary Search and Merge Sort Flashcards
1
Q
Binary Search
A
An efficient algorithm for finding an element in a sorted array
2
Q
Binary search requires a sorted array T or F
A
T
3
Q
What is the calculation to find M
A
(L+R)/2
4
Q
What if a[M] == target
A
If the target is equal to M it means we have already found it. Return M (this means the target is at index M)
5
Q
What if a[M]> target ?
A
Eliminate the right half and move left
( set R = M-1)
6
Q
If a[M] < target ?
A
Move right set (L = M + 1)
7
Q
What do you do once you found the target?
A
If found at index 4 return M = 4.
8
Q
What would I use if the array is unsorted?
A
- Linear Search (O(n) time complexity)
This checks each element one by one - Sort the array first (O(n log n) using QuickSort/Merge Sort and then apply Binary Search
9
Q
A
