E-learning -- Algorithms and Binary Search -- Test A

Algorithm --- Binary Search

In this module, you will learn

1. basic concepts of algorithms

2. how to use binary search to solve problems in the real world

Pre-test: Algorithms

Why take pre-test?

This is a pre-test for basic concepts of algorithms. Your performance will not be included in your final score. However, I would like to see you take this pre-test seriously, because this will be a good chance to check where you are on the topic you are going to learn.

What is an algorithm?

  • An algorithm is a set of step-by-step instructions for solving a problem or completing a task.
  • An algorithm is a term used in the field of math, which is usually used in equation solving.
  • An algorithm is a fact people need to memorize.

When can we use algorithms to solve problems?

  • We use algorithms to solve problems in some fields such as math, physics, chemistry... etc.
  • Using algorithms to solve problems has been widely applied in our lives. We can use algorithms to solve everyday problems.
  • We use algorithms to solve high-technology problems.

The difference between a linear search and a binary search is:

  • A binary search
    looks for a value by checking the element in the middle of an array
  • A linear search
    looks for a value in a linear sequence

Algorithms in Your Life

What are algorithms and why are they important?

An algorithm is a set of step-by-step instructions for solving a problem or completing a task. In computing, programmers write algorithms to instruct the computer how to perform a task.

Please watch the video (0:00 to 4:39) for more information on algorithms in life and in computer science.

Are the efficiencies of algorithms measurable?

  • Yes, the efficiencies of algorithms are measurable. However, the majority of the algorithms have the same efficiency.
  • Yes, the efficiencies of algorithms are measurable. Some of the algorithms are more efficient than others.
  • No, the efficiencies of algorithms are NOT measurable.
  • No, only a few algorithms can be measured.

Algorithms --- Problem Solving and Computational Thinking

Computational thinking is ubiquitous and has been integrated by the Next Generation Science Standards (NGSSin the Math and Engineering standards in as early as elementary grade levels. As a central component of computational thinking, using algorithms to solve problems has been widely applied in our lives. 

We all have used algorithms to make life easier. One such example is finding a word in a dictionary (a paper-based dictionary, sorted alphabetically). Have you ever read through the whole section N in a dictionary to find the word Never? Most people would say "Never!".

Normally, if you are looking for the word Never in a dictionary, you would flip to the middle of the letter N section and determine:

a. if the word you're looking for is on the page you flipped to,

b. if the word is in the first half of the N section, 

c. if the word is in the second half of the N section. 

You would continue this process by flipping to the middle of the next smaller half section until the word is found. This type of searching behavior is very similar to an algorithm used frequently in computer science: binary search, which can greatly enhance the efficiency of finding the word.  

Computer Scientists have developed a variety of such problem-solving models--often called algorithms--to optimize the efficiency of solutions. In the next section, we will learn more about the binary search algorithm. 

Before you learn about the binary search,  please complete the following question as a pre-test --- put the sentences in correct order to indicate how we use binary research to locate a value/item in a sorted collection/list.

  • Find the maximum value and the minimum value of a sorted collection/list.
  • Get the average of the maximum value and the minimum value.
  • If the average number is lower than the item/value you need to locate, set the minimum number to be one larger than the average number. If the average number is higher than the item/value you need to locate, set the maximum number to be one smaller than the average number.
  • Repeat the present two steps until you locate the item/value.

Binary Search

Binary search and linear search

Binary search is a useful algorithm for problem solving. Before we go into the details of binary search, please click the link below and play the guessing game.

Binary research works by repeatedly dividing in half the portion of the list that could contain the item until you've narrowed down the possible locations to just one. 

Linear research sequentially moves through a list looking for the item.

In the guessing game you played, which algorithm is more efficient to locate the number? 

  • Binary search
  • Linear search

Basic concepts of binary search

In the field of computer science, a frequently used algorithm for locating an item in a sorted list is Binary Search. 

It has similarities with the method that you use to find a word in a dictionary. It works by repeatedly dividing in half the portion of the list that could contain the item until you've narrowed down the possible locations to just one.

Please watch the YouTube video below for a detailed explanation of binary search.

Example

Your friend Sasha needs to look up for a sentence in a book which has 100 pages. You know where the sentence is, but you want to see your friend practice binary search algorithm. So you decide to play a game with Sasha. She will choose a page to see if the sentence is there, and if she's wrong, you will tell her to go higher or lower. The following steps indicate what she is going to do:

Step 1.    Set the minimum number to be 1, and the maximum number to be 100, 

Step 2.    Guess the average of 1 and 100, rounded down so that it is an integer. The average of 1 and 100 is 50, so you let your friend go to page 50 to see if the sentence is there.

Step 3.    If she got the number, stop. She found it!

Step 4.    If the average number she got was too low, set the minimum number to be one larger than the average number. So if she guessed 23 and it was too low, set the minimum number to be 24.

Step 5.    If the average number was too high, set the maximum to be one smaller than the average number. So if she guessed 78 and it was too high, set the maximum number to be 77.

Step 6.    Go back to Step 2.

Worked example 1

There are two flavors for a jar of lollipops you have: chocolate and strawberry. However, there's only 1 chocolate flavored lollipops, and the rest 49 lollipops are all strawberry flavored. Your friend Sasha likes the chocolate flavored lollipop, and you think it's a good time for her to practice binary search algorithm. So you number all the lollipops from 1 to 50 and let Sasha guess which one is chocolate flavored. She will pick a number from 1 to 50 to see if she can get the lollipop she likes, and if she's wrong, you will tell her to guess a bigger number or smaller number.  What should she do?

Step 1.    Set the minimum number to be 1, and the maximum number to be 50,  

Step 2.    Guess the average of 1 and 50, rounded down so that it is an integer. The average of 1 and 50 is 25. So you let your friend pick the 25th lollipop to see if that's the lollipop she wants.

Step 3.    If she got the number, stop. She found it!

Step 4.    If she got a number smaller than the lollipop's, set the minimum number to be one larger than the guess. If she guessed 17 and it was too low, set the minimum number to be 18.

Step 5.    If the average number was too high, set the maximum to be one smaller than the guess. So if she guessed 38 and it was too high, set the maximum number to be 37.


There is one more step needed. Do you know what that step is? Please type it down.

Question 1

When we use sorting algorithm to solve problems in the real world, can we set the minimum number to be an integer other than 1? 

  • No, the minimum number has to be 1.
  • Yes, the minimum number can be an integer other than 1.

Worked example 2

The other day Sasha walked into a mall and got attracted by a gorgeous jacket behind a shop window. She rushed in and found 30 jackets folded on the shelf. They were exactly the same but one of them was on sale. Surprisingly, the shopping assistant seemed to think it was a good time for Sasha to practice binary search. She numbered all the jackets from 0 to 29 and let Sasha guess which one was on sale. Sasha needed to pick a number from 0 to 29 to see if she picked the right jacket, and if she were wrong, the shopping assistant would tell her to go higher or lower. What should Sasha do?

Step 1.Set the minimum number to be 0, and the maximum number to be 29, 

Step 2.Guess the average of 0 and 29, rounded down so that it is an integer. The average of 0 and 29 is 14. So Sasha pick the jacket with number 14 to see if it's on sale.

Step 3.If she got the number, stop. She found it!


There are 3 steps left. What are they?

Question 2

Now it's time to check if you fully mastered binary search!


One day you go to an animal shelter with Sasha. Sasha wants you to guess which puppy she is going to take home. There are 40 puppies and you number them from 1 to 40 to guess which one is Sasha's favorite. If you are wrong, Sasha will tell you to go higher or lower. What steps are you going to take by using binary search algorithm?

Hint

Hint: There are 6 steps you need to take.

Question 3

In summary, algorithms are step-by-step instructions for performing tasks. 


Assume there is a list of x items and you need to locate an item from that collection. How can you use the binary search algorithm to solve this question? Remember to use variables to represent numbers.

Self-assessment 1

On a scale of 1 to 10 with 1 being the most negative, and 10 being the most positive, how would you rate your level of understanding what you learned in this module?

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

Quiz

What is an algorithm?

  • An algorithm is a set of step-by-step instructions for solving a problem or completing a task.
  • An algorithm is a term used in the field of math, which is usually used in equation solving.
  • An algorithm is a fact people need to memorize.

When can we use algorithms to solve problems?

  • We use algorithms to solve problems in some fields such as math, physics, chemistry... etc.
  • Using algorithms to solve problems has been widely applied in our lives. We can use algorithms to solve everyday problems.
  • We use algorithms to solve high-technology problems.

What is linear search?

  • A linear search repeatedly divide in half the portion of the list that could contain the item.
  • A linear search sequentially moves through your collection (or data structure) looking for a matching value.

The maximum number of comparisons the linear search performs in searching a value in an array of size N is N.

  • The maximum number of comparisons the linear search performs in searching a value in an array of size N is N.
  • The maximum number of comparisons the linear search performs in searching a value in an array of size N is not N.

The binary search does not work unless the array is sorted.

  • The binary search does not work unless the array is sorted.
  • The binary search works when the array is unsorted.

The difference between a linear search and a binary search is:

  • A binary search
    looks for a value by checking the element in the middle of an array
  • A linear search
    looks for a value in a linear sequence

Self-assessment

Self-assessment 2

On a scale of 1 to 10 with 1 being the most negative, and 10 being the most positive, how would you rate your level of understanding what you learned in this module?

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

Thank you for your time!

This is an anonymous online class. Your performance will be analyzed and used in Carnegie Mellon University's course "E-Learning Design Principle".