English National Curriculum:
Key Stage 2
Tooltip content
To use technology purposefully to create, organise, store, manipulate and retrieve digital content.
learning objectives
Tooltip content
To understand the importance of searches and binary searches.
success criteria
- I can explain what a binary search is.
- I understand why binary searches are used.
- I understand that conditional statements are used to eliminate other values.
top tips
- Binary searches are used to search for something specific in a list (array).
- A binary search does not need to go through everything on a list. This is because it halves the amount of data that needs to be searched with each step.
- Data in a list must be ordered before a binary search is performed.
Common misconceptions
- You can do a binary search on any list or array.
- A list or array must be sorted before the binary search starts.
List
Binary
Binary Search
Lists are used to hold a series of Memory Boxes. In computing, they are called Arrays.
For example, the array below shows information about the exam scores of 6 students. The indices or locations of elements in the list, help us locate each student, and the value at a particular index shows their exam score.
A division into two groups or classes that are considered diametrically opposite. Primarily shown as a number system based only on the numerals 0 and 1 : a binary
A search algorithm that finds the position of a target value within a sorted list (array). Binary search compares the target value to the middle element of the array.
Previous Knowledge
Lists are a collection of memory boxes (We use the index to index to indicate their locations) and are made from three part.
Name, this is given to the list. Similar to a memory box this name is used to identify the list when it is needed. The name can also help to identify the content of the list. For example a list of animals could be called AnimalList or animal_list
Elements: these are objects within the list. These can be of various types of data or even collections of data but should be grouped in a list for a particular reason. For instance in a school students could be grouped into class lists with a new list for each class.
Index: refers to a number we use to reference the location of an element in the list. Every element in a list is given a position number. The index is iterative and each element after the last is given the next appropriate value i.e 1, 2, 3, 4, 5. Please also note that some languages start their index form 0.
TOPIC BACKGROUND READING
A linear search is the simplest method of searching a list. Starting at the beginning of the data set, each item of data is examined until a match is made. Once the item is found, the search ends. This can be incredibly slow if the element is at the end of a list and is not an efficient use of time
Binary search is an efficient algorithm for finding an item from a sorted list of items. 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.
