4.3.4 Search Algorithms Flashcards
Define an algorithm.
A set of instructions which completes a task in a finite time and always terminates.
Determine a search algorithm.
Finds the location of a certain item in a list or verifies that the item is in the list.
Outline the different types of search algorithms.
Linear, binary and a binary tree search.
Outline when a linear search is best used.
On any unordered list.
What is the time complexity of a linear search?
O(n)
What occurs in a linear search?
Each item is compared sequentially to the target.
When is a binary search best used?
On an ordered list.
What happens if a list is unordered, and you wish to use a binary search on it?
It must be sorted by a sorting algorithm.
What is the process of a binary search?
Looking at the midpoint in a list and determining if the target is higher or lower than the midpoint.
What is the time complexity of a binary search algorithm?
O(logN)
When is a binary search best conducted?
On any ordered binary tree.
What is a tree?
An acyclic, connected graph.
What is a binary tree?
A rooted, ordered tree in which each node has 0, 1, or 2 children.
