Searching algorithms: linear and binary search

Learn it by playing

Answer these questions to earn energy, then fish and explore. No account needed.

For educators: ready-to-use lesson slides, revision notes for Searching algorithms: linear and binary search (KS3 Computing, Computer Science) — use them in your lesson, or run the topic as an interactive class activity your learners play as a live game.

Lesson notes

Introduction to Search Algorithms

A search algorithm finds the position of a target value within a list of items.
Two common search algorithms are linear search and binary search.
Linear search checks each item in order until the target is found or the list ends.
Binary search repeatedly divides a sorted list in half to locate the target.
The choice of algorithm affects speed and efficiency, especially with large data sets.

Linear Search

Linear search starts at the first element and compares each element with the target.
It works on unsorted or sorted lists.
In the worst case, it checks every element, so it takes n comparisons for a list of n items.
Its time complexity is O(n) – linear time.
It is simple to implement but slow for large lists.
Best used when the list is small or unsorted.

Binary Search

Binary search requires the list to be sorted in ascending order.
It compares the target with the middle element of the list.
If the target is less than the middle, the search continues in the left half; if greater, in the right half.
This process repeats, halving the search area each time.
If the search area becomes empty, the target is not present.
It runs in O(log n) time – logarithmic time.
For a list of 1,000,000 items, binary search needs at most about 20 comparisons, while linear search may need up to 1,000,000.

Binary Search Step-by-Step

Set low to 0 and high to n-1 (the first and last indices).
While low ≤ high, calculate mid = (low + high) / 2 (rounded down).
If the middle element equals the target, return mid.
If the middle element is less than the target, set low = mid + 1.
If the middle element is greater than the target, set high = mid - 1.
If low > high, the target is not found.

Comparing Efficiency

Linear search time grows proportionally with list size (O(n)).
Binary search time grows logarithmically (O(log n)).
For small lists, linear search may be faster due to less overhead.
For large sorted lists, binary search is dramatically faster.
Binary search requires the list to be sorted, which adds an initial cost if not already sorted.

When to Use Each Algorithm

Use linear search when the list is unsorted or small.
Use linear search when you need to find all occurrences of a value.
Use binary search when the list is sorted and large.
Use binary search when you need the fastest search time.
If the list is frequently updated, sorting overhead may make linear search more practical.

Key Terms

Array – a collection of items stored at contiguous memory locations.
Sorted – arranged in ascending or descending order.
Target – the value being searched for.
Index – the position of an element in an array (starting at 0).
Time complexity – a measure of how the running time grows with input size.
O(n) – linear time; O(log n) – logarithmic time.

Common Mistakes

Forgetting to sort the list before using binary search.
Using mid = (low + high) / 2 without rounding down (integer division).
Not updating low or high correctly, causing infinite loops.
Assuming binary search works on unsorted data.
Confusing index with value when comparing.

Slides

Step through every slide for this topic — plus flashcards and revision notes — with a free account.

Practice questions

Free preview — 8 of 59 questions. Sign up to see them all.

1.What is the main requirement for binary search to work correctly?
Easy
- AThe data must be sorted
- BThe data must be unsorted
- CThe data must be stored in a hash table
- DThe data must be small
2.Linear search requires the data to be sorted.
Easy
True or false?
3.Which search algorithm is generally faster on a large sorted list?
Easy
- ABinary search
- BLinear search
- CBoth are equally fast
- DIt depends on the programming language
4.Arrange the steps of a binary search on a sorted array in the correct order:
Easy
- Compare the target with the middle element.
- If the target is less than the middle, search the lower half.
- If the target is greater than the middle, search the upper half.
- If the target equals the middle, return its position.
5.Which of the following are true about linear search? (Select all that apply)
Easy
- AIt checks each element in order.
- BIt requires the data to be sorted.
- CIt works on unsorted data.
- DIt is usually slower than binary search on large lists.
- EIt always starts from the middle of the list.
6.Given the sorted list [2, 5, 8, 12, 16, 23, 38], what is the first element compared to when searching for 23 using binary search?
Medium
- A12
- B16
- C23
- D38
7.In binary search, after comparing the target to the middle element and finding it is greater, what happens next?
Medium
- AThe lower half is eliminated and the search continues in the upper half.
- BThe upper half is eliminated and the search continues in the lower half.
- CThe search stops immediately.
- DThe entire list is searched again.
8.Binary search can be used on an unsorted list if you first sort it.
Easy
True or false?

Revision notes

## Searching Algorithms: Linear & Binary Search ### Linear Search - **What it is**: Checks each item in a list one by one until the target is found or the list ends. - **Works on**: Any list, sorted or unsorted. - **Steps**: Start at the first item, compare with target, if not match move to next, repeat. - **Time**: Worst case, it checks every item, so for a list of n items it takes up to n steps (O(n)). - **When to use**: Small lists or when data is unsorted. ### Binary Search - **What it is**: A fast search that repeatedly halves the search area. - **Requirement**: The list must be **sorted** (ascending order). - **How it works**: 1. Compare target with the middle element. 2. If equal, done. 3. If target < middle, search the left half. 4. If target > middle, search the right half. 5. Repeat until found or the search area is empty. - **Time**: Each step halves the list, so it takes at most log₂(n) steps (O(log n)). Much faster than linear search for large lists. - **When to use**: Large sorted lists where speed matters. ### Comparison - **Speed**: Binary search is faster than linear search except for very small arrays. - **Trade-off**: Binary search requires the list to be sorted first, which costs time if not already sorted. - **Example**: For 1,000,000 items, linear search may take 1,000,000 steps; binary search takes at most 20 steps (since 2^20 ≈ 1,000,000). ### Key Points to Remember - Always check if the list is sorted before using binary search. - Binary search eliminates half the remaining items each step. - Linear search is simple but slow for large lists. - Choose the algorithm based on data size and whether data is sorted.

Linear search: A search algorithm that checks each element in a list sequentially until the target is found or the list ends.
Binary search: A search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.
Sorted array: An array where elements are arranged in a specific order, typically ascending (e.g., A0 ≤ A1 ≤ ... ≤ An-1).
Time complexity: A measure of how the number of steps an algorithm takes grows with the size of the input. Linear search is O(n), binary search is O(log n).
O(n): Big O notation indicating that the time grows linearly with the number of elements n.
O(log n): Big O notation indicating that the time grows logarithmically with the number of elements n, meaning each step halves the search space.

Flashcards

What is a linear search?

A linear search checks each element in a list one by one from the start until the target is found or the list ends. It does not require the list to be sorted.

What is a binary search?

Binary search is an algorithm that finds a target value in a sorted array by repeatedly dividing the search interval in half. It compares the target to the middle element and eliminates half of the remaining elements each step.

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

The array must be sorted in ascending order (or descending, depending on implementation) before binary search can be applied.

Describe the first step of a binary search on a sorted array.

Compare the target value to the middle element of the array. If they match, return the position. If not, decide which half to continue searching in based on whether the target is less or greater than the middle element.

In binary search, if the target is less than the middle element, which half is searched next?

The lower half (elements with indices less than the middle index) is searched next.

In binary search, if the target is greater than the middle element, which half is searched next?

The upper half (elements with indices greater than the middle index) is searched next.

What happens if the search interval becomes empty in binary search?

If the remaining half is empty, the target is not in the array, and the search terminates as unsuccessful.

What is the time complexity of binary search in the worst case?

Binary search runs in logarithmic time, O(log n), where n is the number of elements in the array.

How does the number of steps in binary search grow as the size of the sorted array doubles?

The number of steps increases by only 1 (since log2(2n) = log2(n) + 1). For example, searching 8 elements takes at most 3 steps, and 16 elements takes at most 4 steps.

How does the number of steps in linear search grow as the size of the list doubles?

The maximum number of steps doubles as well, because linear search may need to check every element. So if a list has n elements, worst-case steps are n.

Which search algorithm is faster for large sorted arrays: linear or binary?

Binary search is faster for large sorted arrays because it has O(log n) time complexity compared to linear search's O(n).

When might linear search be preferred over binary search?

Linear search is preferred for small arrays or when the data is unsorted, because binary search requires the array to be sorted first.

What is the main disadvantage of binary search compared to linear search?

The main disadvantage is that binary search requires the array to be sorted, which may add extra cost if the data changes frequently.

Define the term 'logarithmic time' in the context of binary search.

Logarithmic time means the number of operations grows proportionally to the logarithm of the input size. For binary search, the worst-case number of comparisons is O(log n).

What does the variable 'm' represent in the binary search algorithm?

'm' is the index of the middle element of the current search interval, calculated as L + floor((R - L) / 2).

In the binary search procedure, what are the initial values of L and R?

L is set to 0 (the first index) and R is set to n-1 (the last index), where n is the number of elements in the array.

What is the termination condition for an unsuccessful binary search?

The search terminates unsuccessfully when L > R, meaning the search interval is empty.

Give an example of a binary search on a sorted array of 5 elements: [2, 5, 8, 12, 16], searching for 12. Show the steps.

Step 1: L=0, R=4, m=2 (value 8). 8 < 12, so L=3. Step 2: L=3, R=4, m=3 (value 12). 12 == 12, return index 3.

What is the maximum number of comparisons needed to find an element in a sorted array of 1,000,000 elements using binary search?

At most about 20 comparisons, because log2(1,000,000) ≈ 19.93, so the worst case is 20 comparisons.

What does 'half-interval search' mean?

It is another name for binary search, because each step eliminates half of the remaining search interval.

What is the time complexity of linear search in the worst case?

Linear search has a worst-case time complexity of O(n), where n is the number of elements, because it may need to check every element.

Why is binary search not suitable for unsorted data?

Because binary search relies on the order of elements to decide which half to discard. If the data is unsorted, the middle element gives no reliable information about which half contains the target.

What is the key difference between linear and binary search in terms of data requirement?

Linear search works on any list, sorted or unsorted, while binary search requires the list to be sorted.

If you have a sorted array of 100 elements, what is the maximum number of steps binary search will take?

At most 7 steps, because log2(100) ≈ 6.64, so the worst case is 7 comparisons.

Unlock all 59 questions, flashcards & more

Create a free account to see every question, the slides, flashcards and revision notes for this topic.

Past papers

Past-paper practice for this topic is coming soon.

Coming soon