Binary Search (CS26)

Learning Scenario Identity
Title	Binary Search
Creator	JYU
Length	45 minutes – 1 hour
Main idea/description	The objective of the class is to show through play how a searching algorithm could work. The instructions need to be simple and following them should always lead to success.
Target group	3rd-6th grade
Curriculum/learning subjects	Computer Science, Mathematics
Competencies	The students will learn how to use algorithmic thinking and how simple algorithmic principles work. The students are expected to follow steps to achieve the search outcome.
Teachers’ wellness competences	TC2. E-self-management
Learning Scenario Framework
Pedagogical method	PI7.  Goal oriented learning (Be persistent and work towards your goals)
Software/materials	For online learning context, the teacher should have access to a conferencing tool (e.g., Zoom). The chosen platform needs to enable student-student and teacher-student interaction. The teacher needs the ability to assign students into pairs. Alternatively if it is possible, the students can also call one another. However, using a conferencing tool can make it easier for the teacher to monitor the progress of the students and provide support when necessary. The teacher should make sure that the students are comfortable with using the online platforms that are chosen (e.g., by practicing beforehand with students). For this scenario, it is important that the binary search process is divided into small, digestible steps. The teacher should also use simple language and avoid technical jargon. This can help reduce anxiety and confusion among students, making it easier for students to take a more independent stance to studying and carrying out some of the steps without a constant presence from the teacher. This can also be enforced by using positive reinforcement to encourage participation, Praising efforts and providing constructive feedback.
Evaluation tools	The participants’ learning is evaluated through the discussions together with the whole group. Additionally, there is a feedback session at the end, which can also be used to collect information about the students’ learning.
Learning Scenario Implementation
Learning activities (description, duration, worksheets)	The principle of algorithms is explained to the students (attachment 1) and how the algorithms follow certain instructions to always provide a solution regardless of the data that is given to them. The students can be reminded of the human robot exercise and they are advised to closely follow the provided instructions. Assignment 1 The teacher assigns the students into pairs. First one is the searcher and the other one is the answerer. The answerer picks a number between 1 and 50 and writes the number on paper. When they are done, the searcher starts to ask questions and the answerer can only answer ‘yes’ or ‘no’. In the beginning, someone may be inquiring about individual numbers (‘Is it two?’, ‘Is it three?’). If they do not come up with the possibility to narrow the set down by asking questions such as ‘Is it bigger than 10, they can be guided to the right direction. The general idea of the exercise is explained in the following video (for on-site teaching): https://www.youtube.com/watch?v=vV7TR6_moug  Important! Recognize that the students learn at different paces. Allow them to progress through the exercise at their own pace, providing support as needed. Discussion:  – How many guesses did it take to find the right number?  – What kind of tactics did the students have?  – How the number of guesses with the different tactics would change, if the number was between 1 and 1 000? The teacher explains the principle of binary search: If the search range is between 1 and 1 000, it is first important to inquire is the number greater than 500 (middle of the search). After that, the remaining set is divided to half with a similar question and this is continued until the desired number can be reached. Assignment 2 Let’s start with the range from 1 to 1 000. The student practice the binary search and if they desire, they can try out another way of finding the number. The students count how many guesses are needed to find the right number. What happens, if the range is from 1 to 10 000? What about one to million, or one to billion? Discussion:  – What did the students notice about the number of guesses? – Why didn’t the number of guesses grow very rapidly?  – How many guesses were needed to find a number between one and one million? You can tell the older students about the power of two and how quickly it grows. Each search cuts the number set to half, making it easier to find the desired number. In other words, when the number set doubles, you only need one more question. The picture below explains the power of two. The number two is multiplied with itself as many times as is stated in the exponent. The picture also explains the number of guesses needed for successful binary search. If the number range is 128, you need up to seven questions to find the right number (2 multiplied by itself seven times equals 128). The power of two tells the maximum amount of questions needed to find the desired number. Assignment 3 If there is time, the students can also try in practice whether or not the previously made statement actually makes sense. Finally, have a feedback session at the end where students can share their experiences, what they found challenging, and what they enjoyed. This helps in tailoring future lessons to better suit their needs. Attachment 1 Algorithms are sets of instructions that enable achieving a desired outcome. Basically, these instructions can be any kind of instructions, for example the ones that we can see in cook books. However, usually when algorithms are discussed, we often refer to mathematical instructions or instructions that are meant for a computer to understand. The binary search that we practice here is a search algorithm. Many search and ordering algorithms are used in information technology, but also for example in targeting commercials to people using the Internet.