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, you should write a structured English version of the algorithm, just as you did for bubble sort. You can then turn this into your linear_search function.

1. Take a sequence of integers and a value that is being searched for.

2. Iterate over the length of the list, using position to keep track of the item in the list being looked at.

3. If the item at the position in the sequence is equal to the value being searched for, return the position.

4. If the entire sequence has been iterated over, and the value has not been found, then return False.

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.

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 False.

Again, try this independently first, and ask for help from the teacher if you need to.