Search Algorithms (College Board AP® Computer Science Principles): Flashcards
0Still learning
Know0
- FrontLinear Search
Define linear search.
Was this flashcard helpful?
Cards in this collection (19)
Define linear search.
A linear search checks each element in a list one at a time, from beginning to end, until the target value is found or the end of the list is reached.
What is another name for a linear search?
A linear search is also called a sequential search.
True or False?
A linear search only works on sorted lists.
False.
A linear search works on both sorted and unsorted lists.
What is the best case for a linear search?
The best case is when the target is the first element, needing only 1 comparison.
What is the worst case for a linear search of a list with n elements?
The worst case is when the target is the last element or not in the list, needing n comparisons.
How does the number of comparisons in a linear search grow as the list gets longer?
The number of comparisons grows in proportion to the size of the list.
A linear search can use a _____ flag, initialized to
false, to track whether the target has been located.A linear search can use a found flag, initialized to
false, to track whether the target has been located.A linear search looks for 9 in the list [4, 11, 9, 2, 6]. How many comparisons are made, up to and including finding 9?
3 comparisons are made: 4, 11, then 9.
A linear search looks for 5 in the list [4, 11, 9, 2, 6]. How many comparisons are made?
5 comparisons are made, because 5 is not in the list, so every element is checked.
What value is displayed when this code segment runs?
nums ← [3, 1, 3, 7, 3]count ← 0FOR EACH item IN nums{IF(item = 3){count ← count + 1}}DISPLAY(count)The code segment displays 3, because 3 appears three times in
nums.Define binary search.
A binary search is an algorithm for finding a value in a sorted data set that starts at the middle of the data.
What must be true of a data set before a binary search can be used?
Before a binary search can be used, the data must be in sorted order.
At each step, a binary search eliminates ____ of the remaining data.
At each step, a binary search eliminates half of the remaining data.
Why can a binary search not be used on unsorted data?
On unsorted data the algorithm cannot correctly decide which half to eliminate, so it may fail to find a value that is actually present.
Name two options when you need to search data that is not sorted.
The data must either be sorted first, or a linear search must be used instead.
When does a binary search stop?
A binary search stops when the desired value is found or all elements have been eliminated.
A binary search looks for 25 in the sorted list [3, 8, 12, 17, 21, 25, 30]. Which elements are examined?
The search examines 17 (the middle), then, because 25 is greater, 25 in the upper half, where it is found.
True or False?
Binary search is often more efficient than linear search when applied to sorted data.
True.
Binary search eliminates half of the remaining data at each step, so it usually needs far fewer comparisons.
About how many iterations does a binary search need at most for a sorted list of 1,000 elements?
A binary search needs at most about 10 iterations for 1,000 elements, compared with up to 1,000 for a linear search.
Sign up to unlock flashcards
or