PHP lesson 22: Searching: linear and binary search
UK version. UK school years and UK spelling. · US version of this lesson
A LINEAR search checks each item in turn until it finds the target (or reaches the end). It works on any array, sorted or not. A complete 40-minute PHP lesson (Years 10–11, KS4), from Unit 8: Algorithms and a project. It runs right here in your browser – nothing to install.
- Time
- 40 minutes + 20 min homework
- Year
- Years 10–11, KS4 (ages 14–18)
- You need
- A computer or tablet, paper and a pencil
- Marked
- Instantly, with explanations
For parents: how to use this lesson
You don't need to know PHP yourself. The lesson explains each step on screen, the way Mr Babbage, our Head of Computing, likes it: a worked example first, then a go for your child. Your child predicts what code prints, traces it and puts it in order – marked straight away – and then writes and fixes real PHP in the practice test, where it runs in the browser.
- Read what your child will learn together.
- Press Start the lesson below. Sit with your child for the teaching and the worked example (about 16 minutes): ask them to say what each line does.
- Let them do the practice on their own, then the write-it and fix-it questions in the practice test. When code goes wrong, PHP's message is a clue – let them read it out and try again before you help.
- Finish with the talk question: Why does binary search need the data sorted? Explain with a phone book or dictionary.
Watch out for
- Binary search works on any array. The array must be sorted first.
- Binary search checks every item. Each step halves the part still to search.
Miss Lovelace's tip for home: ask your child to explain one line of their program to you in their own words. If they can explain it, they understand it – and every message from PHP is a clue, not a failure.
What your child will learn
We are learning to write a linear search that checks every item.
Success looks like
- I can write a linear search that checks every item.
- I can trace a binary search on a sorted array.
- I can compare how many steps each search takes.
Key words
algorithm · linear search · binary search · sorted · midpoint · efficiency
What to have ready
- A device with a web browser (PHP runs in the browser – nothing to install)
- Paper for tracing
- A keyboard helps for typing code (a tablet or phone works too)
The big ideas (for the adult)
A LINEAR search checks each item in turn until it finds the target (or reaches the end). It works on any array, sorted or not.
A BINARY search needs a SORTED array. Look at the middle item: if it is too small, throw away the left half; if too big, the right half. Each step halves what is left.
For 1,000 sorted items, a linear search may take 1,000 checks, but a binary search needs at most 10. Choosing the right algorithm matters more than a fast computer.
Worked example – see it
<?php $a = [12, 15, 24, 38, 47, 55]; echo in_array(57, $a) ? "yes" : "no";
It prints:
no
The lesson, step by step
| Part | Time | How it is checked |
|---|---|---|
| Starter | 5 min | Marked by Classfern |
| Teaching input | 8 min | Read, watch and talk |
| See it, then predict | 8 min | Marked by Classfern |
| Put it in order, trace it, check it | 14 min | Marked by Classfern |
| Plenary and exit ticket | 5 min | Marked by Classfern + self-check |
The lesson
It runs here on the page. No sign-up and no names – progress is kept only in this browser. Each visit picks a new mix of questions.
Homework
20 minutes: 5 questions – predict what code prints, trace it or put it in order, and check the key ideas – then a short reflection. New questions every time, all marked instantly.
Write it and fix it: practice tests
The practice tests run real PHP in your browser: write and fix short programs, marked against hidden tests.
Curriculum
National curriculum in England, computing, key stage 4: pupils should be taught to develop and apply their analytic, problem-solving, design, and computational thinking skills.
Contains public sector information licensed under the Open Government Licence v3.0.
Our lessons and questions are our own. They are not written or endorsed by any government department, testing agency or exam board. Classfern is not affiliated with or endorsed by The PHP Group. PHP runs here as php-wasm, under its open-source licences.