Computer Science

an algorithm to search for an item in a sorted data set — it discards half of the remaining data with each comparison and repeats the process until the item is found or until the data set is exhausted

a list of items where the values are in either ascending or descending order

Binary search

Linear search

Comparing searching algorithms

Bubble sort

Merge sort

Insertion sort

Coding sorting algorithms

Practice searching and sorting algorithms

In this unit pupils will have opportunities to analyse, interpret, modify, and implement a range of searching and sorting algorithms. They will have the opportunity to compare the features and efficiency of these algorithms and make suggestions about the most suitable algorithm for a given task.

Searching and sorting algorithms

What is the name of the algorithm that searches a sorted list by repeatedly halving the data set?

searches sorted data by halving each step

items arranged in ascending or descending order

What type of list is required for a binary search to work?

You can perform the binary search as usual.

A binary search cannot be performed on unordered data, even if sorted.

What happens if the data is unordered and you want to perform a binary search?

If less, focus on items after the midpoint.

If greater, focus on items before the midpoint.

Arrange the steps of a binary search algorithm in the correct order:

It eliminates half of the remaining data with each comparison.

Why is binary search typically faster than linear search for large data sets?

Ordered lists have items in a specific sequence; unordered lists do not.

What is the main difference between an ordered and unordered list?

Which of these is an advantage of an ordered list?

When searching for a word in a dictionary, what makes it possible to find the word?

Items are not arranged in any logical order.

Why might searching an unordered list take longer than an ordered list?

a random list of items on a shopping list

Which of these is an example of an ordered list?

What is the name of the algorithm that checks each item in a list one at a time to find a specific item?

Binary search

Lesson outcome