Searching
Class 12 · Computer Science
4 ideas in Class 12 Computer Science, explained in plain words, with games and quizzes to practise.
Linear Search
Part of: Step-by-step searching
Linear search checks the list from the first item onward, comparing each one with the wanted key. It stops with success at the first match, or reports failure after the whole list is crossed. Finding the first item takes one comparison, while finding the last item or missing the key takes as many comparisons as there are items.
Why it matters. Linear search works on any order, so it is the fallback when lists are small or shuffled. Counting its comparisons teaches best and worst cases, the first step of judging any algorithm.
Key words
- Searching
- : Locating a wanted item and reporting its position.
- Key
- : The wanted item being searched for.
- Comparison
- : One check of a list item against the key.
- Sequential Search
- : Another name for linear search, item after item.
Try it in two minutes
- Line up seven number cards and search for the fourth one.
- Count the comparisons aloud until the match.
- Search for a missing number and count again.
Try at home. Ask your child to search a spice rack item by item and report the comparison count.
Binary Search
Part of: Step-by-step searching
Binary search needs a sorted list. It compares the key with the middle item: a match ends the hunt, a smaller key keeps the first half, and a bigger key keeps the second half. Each failed round halves the area left, so even long lists fall in a few rounds.
Why it matters. Halving beats scanning on big ordered data like dictionaries and directories. Learners who trace halves understand why sorting first can pay off hugely.
Key words
- Binary Search
- : Searching by halving a sorted list around its middle.
- Middle Item
- : The centre card each round is compared with.
- Iteration
- : One round of checking and then halving.
- Sorted List
- : A list arranged in order, needed for halving search.
Try it in two minutes
- Sort seven number cards from small to big.
- Guess the middle card and keep the correct half.
- Repeat until the wanted card is cornered.
Try at home. Ask your child to find a word in a dictionary by halving pages and count the rounds.
Hashing
Part of: Fast lookup with hashing
Hashing turns a key into its slot number with a small formula called the hash function. A common one keeps the remainder left when the key is divided by the table size. The key is stored at that slot, so finding it later needs just one check: compute the slot and compare.
Why it matters. Hashing finds keys without scanning or sorting, which powers fast lookups in real systems. Learners who compute slots by hand see how maths can replace searching.
Key words
- Hashing
- : Placing and finding keys through a computed slot number.
- Hash Function
- : The formula that turns a key into a slot number.
- Hash Table
- : The slots where hashed keys are stored.
- Hash Value
- : The slot number a hash function returns.
Try it in two minutes
- Take an 11-slot empty table and the key 63.
- Divide 63 by 11 and keep the remainder as the slot.
- Store 63 there and find it back with one check.
Try at home. Ask your child to place five family ages into an 11-slot table using remainders.
Collisions
Part of: Fast lookup with hashing
A collision happens when two keys compute to the same slot, like 63 and 19 both landing in slot eight of an 11-slot table. Since one slot keeps one item, the latecomer needs another plan, called collision resolution. A perfect hash function gives every key its own slot, so collisions never occur.
Why it matters. Clashes are the real-world catch in fast lookup. Learners who spot them understand why table size and function choice matter, and what perfect hashing promises.
Key words
- Collision
- : Two keys computing to the same table slot.
- Collision Resolution
- : Finding another slot for a clashing latecomer.
- Perfect Hash Function
- : A function giving every key its own unique slot.
Try it in two minutes
- Compute slots for 63 and 19 in an 11-slot table.
- Note that both want slot eight.
- Ask where the latecomer should go.
Try at home. Ask your child to find two ages among family members that clash in an 11-slot table.
What your child will practise
- Binary Search: Jungle Quick Fire (Quick Fire)
- Collisions: Candy Quick Fire (Quick Fire)
- Collisions: Space Puzzle (Clue Puzzle)
- Hashing: Ocean Puzzle (Clue Puzzle)
- Linear Search: Desert Quick Fire (Quick Fire)
- Quiz: Binary Search (8 questions)
- Quiz: Collisions (8 questions)
- Quiz: Hashing (8 questions)
- Quiz: Linear Search (8 questions)