42. AQA GCSE (8525) SLR7 – 3.1 Binary search

What is the first step in a binary search algorithm?

• Sort the dataset in ascending order.

• Calculate the midpoint of the dataset.

• Divide the dataset into two halves.

• Compare the first item with the search item.

Answer explanation

The first step in a binary search algorithm is to calculate the midpoint of the dataset, not to sort, divide, or compare items.

What condition must be met for a binary search to work?

• The dataset must be divided into two equal halves.

• The dataset must have an even number of items.

• The dataset must be in order of a key field.

• The dataset must contain unique items.

Answer explanation

Binary search requires the dataset to be in order of a key field to work efficiently by comparing the target value with the middle element.

How does a binary search compare to a linear search in terms of efficiency?

• A linear search is more efficient on large datasets.

• A binary search is more efficient on average.

• There is no difference in efficiency.

• A binary search is always faster.

Answer explanation

A binary search is more efficient on average.

What happens if the item you are looking for is lower than the item at the midpoint in a binary search?

• The dataset is re-sorted.

• Repeat the process on the right half of the dataset.

• The search is terminated.

• Repeat the process on the left half of the dataset.

Answer explanation

If the item you are looking for is lower than the item at the midpoint in a binary search, you should repeat the process on the left half of the dataset to continue narrowing down the search.

What type of division is used to calculate the midpoint in a binary search?

• Exponential division

• Modular division

• Floating-point division

• Integer division

Answer explanation

Integer division is used to calculate the midpoint in a binary search by dividing the sum of the low and high indices by 2, resulting in a whole number without decimals.

What happens when the left and right pointers are the same value in a binary search?

• The search algorithm restarts.

• The dataset is re-sorted.

• A new midpoint is calculated.

• The item is either found at the pointer or not in the list.

Answer explanation

When the left and right pointers are the same value in a binary search, the item is either found at the pointer or not in the list.

How many checks would a linear search have performed in the provided example with a dataset of eight items?

• 3 checks

• 4 checks

• 8 checks

• 5 checks

Answer explanation

A linear search checks each item in the dataset one by one until finding the target. With 8 items, it would perform 5 checks to find the target.

What is required before starting a binary search according to the video?

• A sorted list of items

• A list of items with unique values only

• A list of items in any order

• A list of items with an odd number of elements

Answer explanation

Before starting a binary search, a sorted list of items is required to ensure the algorithm works correctly by efficiently narrowing down the search space.

What is the main advantage of a binary search over a linear search?

• It can work with unsorted data.

• It is easier to implement.

• It is more efficient on average.

• It requires less memory.

Answer explanation

The main advantage of a binary search over a linear search is that it is more efficient on average, as it has a time complexity of O(log n) compared to O(n) for a linear search.

In the example provided, what is the initial value of the left pointer?

• 3

• 7

• 1

• 0

Answer explanation

The initial value of the left pointer in the example provided is 0, as mentioned in the correct answer choice.