Flashcards in Invitation: Chapter 3 Deck (7)
When doing a sequential search, what are the best, worst, and average cases?
How does binary search work?
We look in the middle, decide which way to go, look in the middle of that part, decide which way to go within the part, and keep repeating this pattern until we have found what we are looking for
What is the worst case in a binary search? What is the average case?
worst case=lg n
average case=(also) lg n(although exact value is smaller than in the worst case)
Pattern Matching: what is the best case?
1: what we are looking for is the first pattern on the list.
2: the first pattern of what we are looking for appears nowhere on the list
Pattern Matching: what is the worst case?
1: the pattern we are looking for appears continuously throughout the whole list, but never completely
2: the pattern appears absolutely everywhere on the list
explain selection sort algorithm
We have a list of numbers, and draw a vertical line at the far end of the list. The left side of this line represents the unsorted numbers. The right side represents the sorted numbers. Take the largest number on the unsorted side and switch it with the right-most number. Then move the vertical line one to the left. Repeat this process until there are no more numbers on the unsorted side.