Step 3: Performing a Linear Search

A linear search algorithm goes through each item in the list one by one, and checks to see if the item is the target that's being searched for.

We'll use a recursive function (a function that runs itself inside itself) instead of a counting loop - this is so that we can add a time delay to simulate each query taking some time. This will show the cost of the algorithm. In reality, computers need to expend work to perform any task, so by adding this time delay, we are making that cost more visible. We'll make each rectangle light up as it is queried. If we don't make the query take a little time, then we won't get to see the queries happen since they'll all happen at once (remember the rectangles being created with the counting loop).

With each query we'll add 1 to the query counter, and then check the rectangle in the position of the list that's equal to the query counter, e.g. with 1 query we'll check the first rectangle, and with 32 queries we'll check the 32nd rectangle. If the rectangle's height = the target height, then we'll tell the user we've found their rectangle and colour it green, or else we'll colour it red and move on to the next rectangle in the list. We'll also tell the user how long it took to find their rectangle.

Start by creating a new property number variable for "queries" and set it to 0. Then create a function to go inside this function, and name it "check next rectangle".

In the "check next rectangle" function, we'll create inputs (also known as parameters) which are local variables used specifically for passing data to a function when the function is called. Click on the cog icon on the "check next rectangle" function, and drag an input into the inputs block. Name the input "check list position". We'll use this input variable as a number that tells the function the position in the list to check, e.g. "check list position" = 1 will make the function check the first item in the list.

You'll notice the function call now has a slot for a value to be connected. Grab a number block (from Operators) and drag it into that slot. Set it to 1, so that the first list position checked will be 1.

Inside the "check next rectangle" function, we'll increase the number of queries by 1 so that they count up. Grab that variable, and add 1 to it.

Then we'll find the rectangle from the list position the function is checking, and we'll check if the rectangle has the same height as the target we're searching for. Grab "set instance rectangle to" (from Variables), and also grab "in list list, get #" (from Operators) and "number check list position" (from Variables).

To check the rectangle's height, we'll need "if" (from Control flow), "actual height" (from Transform), "instance rectangle" (from Variables), "=" (from Operators), and "number target rectangle height" (from Variables).

If the rectangle does have the same height as the target, then we'll make it green and tell the user how long it took to find it. Grab "set colour of shape" (from Draw), "instance rectangle" (from Variables), "100 milliseconds have passed" (from Control Flow), "print" (from Control Flow), "create text with" (from Operators), the empty text block (from Operators), "number queries" (from Variables), "number milliseconds it takes to query the list" (from Variables), "x" (from Operators), and "÷" (from Operators). Arrange those blocks as below, and type "The search took this many seconds:" into the empty text block.

But if the "check next rectangle" function doesn't find the right rectangle, it will have to move on to the next rectangle. Add an "else" part to the "if" block by clicking on its cog, and dragging the else block inside.

In here we'll make the rectangle coloured red, and then in a certain amount of milliseconds (determined by the variable "milliseconds it takes to query the list") we'll call the function "check next rectangle" with the "check list position" input set to "number check list position + 1". Grab "set colour of shape" (from Draw), "instance rectangle" (from Variables), "100 milliseconds have passed" (from Control Flow), "number milliseconds it takes to query the list" (from Variables), "number check list position" (from Variables), "+" (from Operators), and "1" (from Operators). Arrange them as shown below.

This is a recursive function (meaning it reoccurs) because it runs itself inside itself. If you aren't careful, you can get these stuck in an infinite loop!

Now our linear search is complete, hit Play to test it out. Each rectangle should light up until it finds the target.