Implementing linear search
In this step you’re going to implement your own basic version of linear search, and then write a more efficient algorithm that is optimised to work on sorted lists.
The algorithm in English
To begin with, we can write a structured English version of the algorithm, just as we did for bubble sort. You can then turn this into your
- Take a
sequenceof integers and a
valuethat is being searched for.
- Iterate over the length of the list, using
positionto keep track of the
itemin the list being looked at.
- If the
sequenceis equal to the
valuebeing searched for, return the
- If the entire
sequencehas been iterated over, and the
valuehas not been found, then return
Implementing the algorithm
A quick note, before you get started: there are three main ways to iterate over a list of values, and keep track of your position in the list. Have a look at the examples below, and you can choose the method you are most comfortable with.
This first example uses a
while loop along with a counter variable called
position. The loop repeats and increments the position variable until it matches the last element of the list.
sequence = ['A','B','C','D'] #Example 1 - A while loop position = 0 while position < len(sequence): print(sequence[position], "is at position", str(position)) position += 1
The second example does exactly the same thing, but using a
for loop. The duration of the loop is set to the length of the list.
#Example 2 - A for loop over a range for position in range(len(sequence)): print(sequence[position], "is at position", str(position))
This final example is specific to Python, which has a built in function
enumerate. This function maps a number to each list item, and means you don’t need a separate counter variable. While this looks very similar to the previous example, it also allows you to do some clever things. For example
enumerate(sequence,1) would label each element starting at 1 rather than 0, which might be useful for communicating the position to human beings.
#Example 3 - The enumerate function for position, item in enumerate(sequence): print(item, "is at position", position)
Now have a go at implementing your own linear search function, in a way that would work on an unsorted sequence of integers.
Share your code in the comments section and help each other out if anyone gets stuck.
Working with sorted lists
Now that you have implemented a basic search, its performance can be improved by altering it to work on sorted lists.
Remember you just need to add an extra conditional into your code, so that if the
item in the list being looked at is larger than the
value being searched for, then the function can return
Again, try this independently first, and ask for help in the comments if you need to.