Linear Search
Linear search, also known as sequential search, is a simple searching algorithm that checks each element of a list in order until a match is found or the entire list has been traversed.
Algorithm Steps
- Start at the beginning of the list.
- Compare the target value with the current element.
- If the target value matches the current element, the search is successful and the position of the element is returned.
- If the target value does not match the current element, move to the next element in the list.
- Repeat steps 2-4 until a match is found or the end of the list is reached.
Time complexity – O(n)
Because linear search potentially needs to check each item (n) in the list once in the list, the time complexity is O(n)
Space complexity O(1)
The space complexity of a linear search algorithm is generally O(1), which means it uses a constant amount of additional memory regardless of the size of the input data. This is because a linear search does not require any additional data structures or memory allocation that scales with the size of the input.
You may use a few variables for control and temporary storage, but the memory usage remains constant and doesn’t depend on the size of the input data.
Example Python Code Implementation of Linear Search
How does my implementation above differ to standard Python in the way it handles linear search?
Programming Challenges
Challenge 1 – find the highest
Write a function find_highest(list) that that takes a list and returns the index of the highest value in the list. If the list is empty, return -1
Challenge 2 – find an item
Write a function find(list, target) that takes a list and a target value as an input value and returns the index of the first occurrence of the target.
If the target isn’t found, return -1
Challenge 3 – find all items
Write a function find_all(list, target) that that takes a list and a target value as an input value and returns a list of indexes of all the occurrences of the target value.
Challenge 4 – find all higher
Write a function find_all_higher(list, target) that that takes a list and a target value as an input value and returns a list of the values of all items that are higher than the search item
Challenge 5 – find between
Write a function find_all_between(list, lower, upper) that that takes a list, a lower value bound and an upper value bound as input values and returns a list of the values of all items that are exclusively between the two values.