Step 4: Performing a Binary Search

A binary search algorithm goes to the middle point of the list, checks if the item at the middle is smaller or larger than the target, and then narrows down the search by checking the middle of the next smaller quarter, and keeps dividing by half until it finds the target.

We'll keep our linear search code, but we'll use new code for a binary search. Create a new function definition named "Perform binary search", and inside the "target a rectangle" function, replace the function call for "Perform linear search" with the function call for "Perform binary search".

The "perform binary search" function will set the number of queries to 0, and then call its own recursive function named "binary check rectangle" that has inputs for a high number and a low number. The "binary check rectangle" function will find the middle of those two numbers and check that item in the list. If that item is the rectangle with the height of the target, then we'll tell the user how long it took to find that rectangle, or else we'll adjust the high or low numbers depending on whether the target is bigger or smaller than the middle item.

Grab "set number queries" (from Variables), "0" (from Operators), create a new function definition (from Functions) named "binary check rectangle", and grab that function call. Arrange the blocks as shown:

Then click on the cog for the function "binary check rectangle" and drag 2 inputs inside. Name those "high position" and "low position", and in the function call, set the low position to 1, and the high position to "length of" (from Operators) "List list of rectangles" (from Variables).

In the "binary check rectangle" function, we'll set the queries number to increase by 1 (so that they count up), and we'll check the rectangle at the list position halfway between the high position and low position. Grab "set number queries" (from Variables) "+" (from Operators), "1" (from Operators) and join those together.

To get the halfway point between the high and low positions, we'll add them together, divide them by 2, and then round that number. We're rounding it so that if we get something like (13 + 2) ÷ 2, we don't try to find the item at list position 7.5, since there is no position 7.5! In that example it will round up to 8 instead.

Grab "set number check list position" (from Variables), "round" (from Operators), "+" (from Operators) "number high position" (from Variables), "number low position" (from Variables), "÷" (from Operators), and "2" (from Operators).

Then we'll set the instance rectangle to the rectangle at that list position. Grab "set instance rectangle to" (from Variables), and also grab "in list list, get #" (from Operators) and "number check list position" (from Variables).

Now we'll check if the rectangle has the height of the target. 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 it doesn't find the right rectangle, it will have to check if the target is bigger or smaller than the currently checked rectangle. Add an "else" part to the "if" block by clicking on its cog, and dragging the else block inside.

We'll also need another "if" block inside the else section, and this new "if" block will be modified to become "if else if".

In here we'll check if the target height is bigger or smaller than the height of the current rectangle being checked. Grab two "number target rectangle height" blocks (from Variables), two "actual height" blocks (from Transform), and two "instance rectangle" blocks (from Variables). Also grab ">" and "<" from Operators. Arrange them as shown:

If the target height is greater than the current rectangle's height, then we'll colour the current rectangle red, then we'll wait however long the query takes in milliseconds, and we'll call the "binary check rectangle" function: this time with a low position of the current rectangle + 1, and a high position the same as before.

If the target height is less than the current rectangle's height, then again we'll colour the current rectangle red, and we'll wait for however long the query takes in milliseconds. Then we'll call the "binary check rectangle" function with a low position of the same low position as before, and a high position changed to the position of the current rectangle - 1.

This will make the checking process find the middle rectangle, then eliminate half of the list, and check the middle of the other half, repeating that process until it eventually finds the right rectangle. Press Play to see it in action!

Great work! In the next part of this tutorial we'll cover Sorting algorithms. We'll shuffle our list of rectangles and make a big mess that needs to get sorted back in order using a couple of different sorting algorithms.