lesson 3.14.2 linear search

Implementing a Simple Search on an Unordered List

Imagine you've lost your house keys in a messy room. You don't have a map, and the room is a total disaster zone. How do you find them? You pick up one item, check it, put it down, and move to the next. That is a Linear SearchStarts at the beginning of the list and compares each element in turn with the required value until a match is found, or the end of the list is reached. Is the only option with an unordered list (though could be used for any list).! Today, we are going to learn how to teach a computer to look for data in the exact same way - checking items one by one until it finds what it's looking for (or runs out of places to look). It's simple, it's robust, and it's the first step on your journey to becoming a Data Scientist!

Learning Outcomes

The Building Blocks (Factual Knowledge)

Recall that a Linear Search checks every item in a list sequentially from the start to the end.

Describe the difference between the "best case" and "worst case" scenario when searching for an item.

Identify that a Linear Search is necessary when the dataset is unordered (unsorted).

The Connections and Theories (Conceptual Knowledge)

Explain why the efficiency of a Linear Search drops as the size of the dataset increases.

Compare the process of a human searching a room to the computer iterating through a list index by index.

Analyse a trace table to track the values of the loop variable and the current item being checked..

The Skills and Methods (Procedural Outcomes)

Apply the standard Python "for loop" structure to iterate through a list.

Create a function that returns the index of a target item if found, or -1 if not found.

Debug a search algorithm that fails to handle items that do not exist in the list.

Digital Skill Focus: Organising data: Appropriately naming list variables and ensuring test data files are stored in the correct directory.

The Jack in the Haystack

Have you ever tried to find a specific song in a playlist that wasn't sorted alphabetically? You had to scroll down, reading every single title until you spotted the one you wanted. This is the essence of a Linear SearchStarts at the beginning of the list and compares each element in turn with the required value until a match is found, or the end of the list is reached. Is the only option with an unordered list (though could be used for any list)..

In Computer Science, searching is one of the most common tasks we perform. Whether it's finding a username in a database or a contact on your phone, the computer needs an algorithmA 'recipe' or sequence of 'unambiguous' instructions for solving a problem. to locate the data.

The Algorithm

We can visualise this using the "Card Search" logic. If we had a row of face-down cards and wanted to find the Jack of Clubs, the pseudocodeI have no idea what this means algorithm would look like this:

START
   SET target TO "Jack of Clubs"
   SET position TO 1
   
   LOOP through every card in the row
      Turn over card
      IF card is equal to target THEN
         OUTPUT "Found it at position " + position
         STOP (Break the loop)
      ENDIF
      INCREMENT position by 1
   ENDLOOP

   IF card not found
      OUTPUT "Card not found in this row"
END

This is a robust method because it works on ANY list, even if the data is completely jumbled up (unorderedI have no idea what this means).

Translating to Code

Now we know the logic, we can begin to translate this into Python. We need a loopI have no idea what this means (FOR) to move step-by-step through the list, in this case a sequence of numbers, and a selectionI have no idea what this means statement (IF) to check the items.

First, the pseudocode...

SET my_list TO [10, 50, 30, 70, 80, 20]
SET target TO 30
SET found TO False

FOR index FROM 0 TO LENGTH(my_list)
    IF my_list[index] = target THEN
        PRINT "Found it at position " + index
        SET found TO True
        BREAK  <-- Stop looking!
    ENDIF
NEXT index

IF found = False THEN
    PRINT "Item not found"
ENDIF

Task 1 Hero Hunter

It is time to catch a superhero. We are going to build a search engine script step-by-step. Follow the instructions below carefully to build your code block by block.

Get Organised!

Open your Python editor (IDLE or Thonny).

Organise your workspace.

The Setup

First, we need a list of heroes to search through. Copy and paste this list into your lovely clean script:

# Create our list of superheros. Remember - lists start at position '0'.
heroes = ["Superman", "Wonder Woman", "Batman", "Flash", "Aquaman", "Cyborg"]

User Input

Now, ask the user who they want to find. Add this snippet under your list:

# Ask the user which hero they would like to find
target = input("Which hero are you looking for? ")

The Flag

We need a variable to remember if we found them or not. We start by assuming we haven't found them (this is a very common strategy in computing). Add this underneath:

# Obviously, we haven't found them yet
found = False

The Search Engine

Now for the search engine. This loop looks at every index number (0, 1, 2...) in the list in order. Copy this into your script.

# Loop through every item in the list, starting at item 0
for i in range(len(heroes)):
    if heroes[i] == target:
        print("Found", target, "at position", i)
        found = True
        break

The loop will end under two circumstances:

If the search term is located, then the

break

command ends the loop/search early.

If the loop finishes 'normally' when the list runs out. If this happens, found will still be False...

The 'Not Found' Handler

Finally, check the 'flag'. If it is still

False

, the hero wasn't in the list. Add this after the loop (no indentation, please!):

# Fail gracefully
if found == False:
    print("Sorry, I can't find that hero.")

Run It!

Run your code. Give it the filename hero_search.py.

Type Batman (make sure you use a capital 'B'). It should tell you the position.

Run it again and type Joker. (Make sure you use a capital 'J'). It should tell you they are not in the list.

Outcome: A working, interactive Linear Search script.

Efficiency: The Cost of Searching

Does the Linear Search work? Yes. Is it fast? That depends on your luck!

👍 "Best Case" Scenario (lucky)
Imagine you are looking for "Superman" in our list. He is at index 0I have no idea what this means. The computer makes just 1 comparison and stops. This is the best baseI have no idea what this means of the algorithm. It's super fast and it doesn't matter how long the list is.

👎 "Worst Case" Scenario (unlucky)
Now imagine you are looking for "Cyborg" (at the end) or "Joker" (which isn't in the list at all). The computer has to check every single item in the list in order to tell whether the hero is there or not. If the list has 6 heroes, it makes 6 checks. If it had 100 heros, then it would have to make 100 checks and so in. This is the worst caseWhen running an algorithm when it needs to perform the maximum number of operations possible. of the algorithm. It's as slow as it can be and gets slower and slower as the list grows.

Essentially, as the length of the list doubles, so do the number of comparisons that the algorithm needs to make (in the worst case). If the length triples, so does the number of comparisons and so on. Computer scientists call this relationship the time complexityI have no idea what this means of the algorithm. This one isn't very good.

Task 2 The Efficiency Investigation

You are acting as an Analyst whilst you investigate the real world implications of algorithms by looking at the best and the worst case of a linear search. Let's tweak our code from Task 1 to generate a random list of numbers and to add a "counter" so we can demonstrate the theory of best case and worst case.

Get organised!

Your teacher will give you a copy of a recording sheet for you to complete with a pen or a pencil whilst you are carrying out your investigation using the widget in step 2 - no need to use Thonny for this one.

Investigate this

Here is a Python script designed to demonstrate the effect of list size on best and worst case behaviour of a linear search algorithm. Feel free to have a look at the script and the "Code Explainer" underneath if you are interested.

🤔 Code Explainer

Line 1: Import the 'random' library so we can do cool randomness.
Line 2: Set the start value of the items.
Lines 4-10: The linear search implemented as a function.
Line 12: Loop forever.
Line 13: How big shall I make the list?
Lines 14-15: If you just press enter, the I quit
Line 16: Create the list.
Line 17: Randomise the list.
Lines 18-20: Print some stuff.
Line 21: Look for the first item (best case).
Line 22: Print some more stuff.
Line 23: Look for the last item (worst case).

Follow the instructions on the handout.

Consider this...

💭 Did the best case scenario for linear search depend on the size of the list?
💭 Did the worst case scenario for linear search depend on the size of the list?

This algorithm falls within the linear complexity band because as you double the size of the list, the worst case doubles as well. Linear search is great for short, unsorted lists but, as the size of the list increases in size, it become slower and slower.

Outcome: Empirical proof of algorithmic efficiency.

Today you have learnt how to define, trace, and implement a linear search algorithm to locate a specific item within an unsorted dataset by checking each element in turn.