Week 1: Search Problem, Linear Search, Binary Search Flashcards
What is the “Search Problem”?
What are some examples of the search problem?
Finding a phone number of a person in a phonebook (S = phonebook, x = name of a person)
Printing a transcript of a person (S = student records, x = student ID)
Validating variable name (S = variables in a program, x = variable name)
The solution of a problem has two parts, what are they?
What is an algorithm?
How many different ways (algorithms) are there to solve a problem?
What is the SDLC? What are its parts?
What is a good practice for solving algorithms?
What is the algorithm for linear search?
How does one proove the correctness of an algorithm?
What is the correctness of linear search?
What is binary search?
Searching a sorted array by checking whether or not the middle element is the found element and then repeating with the LHS or RHS of the middle depending on whether the middle number was GT or LT the number we want to find.
What is the algorithm for binary search?
What is the correctness of binary search?
In linear search, when would the algorithm return -1?
When i = n. When the while/for loop has iterated over the entire array until the index of i has reached the length of the array (out of bounds)
What are the inputs/outputs for linear search?
What two tests are done for linear search?
i = n
A[i] != x
What are the inputs/outputs of binary search?
What is the order of events in the binary search algorithm?
When does binary search return -1?
In binary search, what happens if:
A[mid] > x
In binary search, what happens when:
A[mid] < x
