11 - Binary search

• Computing
• Upper Secondary (Key Stage 4)
• GCSE

Binary search

/Division and remainders

Division and Remainders

/ Division

// Floor Division

% Modulus

Predict

What do you think the code
will do when run?

RUN

Run the code

Investigate & Modify

Using /, // and %, calculate the following questions using python

What is 703 divided by 34 with no remainder?

1. 23
2. 22
3. 20
4. 34

What is the remainder of 703 divided by 34?

1. 23
2. 22
3. 20
4. 34

What is 90231 divided by 94?

1. 959
2. 959.904255319
3. 90
4. 85

Make

Convert minutes to hours and minutes in python

Begin by prompting the user to input the number of minutes.

Use floor division (//) to calculate the number of hours from the total minutes.

Use modulus (%) to calculate the remaining minutes after converting them into hours.

Print out the result in the format "X hours and Y minutes".

Click here for a blank createwithcode

Solution

Run the code

Searching activity

Predict

What do you think the code
will do when run?

Run

Click here

Investigate and Modify

Experiment with altering the target and array's hard-coded values to investigate their effects

• Replace the array, to cover a range of 1-10 using two "pointers"
  
• Replace target's hard coded value with a user input.

Make

Click here for a blank createwithcode

Create a program to guess a user's number 1-100

You will only tell the program if their number is higher, lower or correct.

Number Guesser Code

Click here

What is the main advantage of using binary search over linear search?

1. Binary search is eaiser to implement
2. Binary search usually runs faster
3. Binary search works on unsorted data
4. Binary search is more suitable for small datasets

What is the result of 17 % 5?

1. 2
2. 3
3. 4
4. 5

In binary search, what is the first step after calculating the midpoint?

1. Check if the midpoint is equal to the target
2. Update the low pointer to the midpoint
3. Update the high pointer to the midpoint.
4. Divide the searrch space into two halves.