Linear Search

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

1. Start at the beginning of the list.
2. Compare the target value with the current element.
3. If the target value matches the current element, the search is successful and the position of the element is returned.
4. If the target value does not match the current element, move to the next element in the list.
5. Repeat steps 2-4 until a match is found or the end of the list is reached.

Interactive linear Search Demonstration

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.

Advantages & Disadvantages of Linear Search

Advantages

• Simple and easy to understand
• Works on both sorted and unsorted lists
• Works well for small data sets
• Useful if you expect the item to be near the beginning of the list

Disadvantages

• Inefficient for large data sets
• Time complexity: O(n), where n is the size of the list
• Can be slow compared to other search algorithms

 

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.