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

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?

Starter Quiz