Not sure which lesson to do first? Find your level and get a plan →

CS Thinking · Computational Thinking · Grade 9-12

Searching

The process of locating a specific item or value within a collection of data using a systematic strategy.


Quick Answer

The process of locating a specific item or value within a collection of data using a systematic strategy. You search whenever a program must answer 'is it here, and where?': a username among accounts, a word in a document, a price in a table. Linear search checks items one by one and works on any list. Binary search halves a sorted list with each comparison, so 1,000,000 sorted items need at most 20 checks instead of up to 1,000,000.

Why This Matters

Search runs constantly behind every app: logging in looks up your username, a spell-checker looks up each word, a store finds a product's price. The strategy decides whether that takes 20 steps or a million. Choosing wrong also breaks things: binary search on unsorted data reports 'not found' for items that are there, and a search with no not-found rule can run past the end of the list.

Intuitive Explanation

Suppose you need the card numbered 37 in a shuffled pile of 100. Nothing about one card tells you where 37 is, so you turn them over one at a time. You might get it on the first card or need all 100; on average about half. That is linear search: it works on any collection, sorted or not, and its worst case grows in step with the size, O(n).

Now the cards are laid out in order, 1 to 100. Turn over the middle card: 50. Since 37 < 50, every card from 50 up is ruled out, and one look removed half the pile. The middle of 1 to 49 is 25, too small, so 37 lies in 26 to 49, and the middle of that range is 37: found on the third look. Even the unluckiest target takes at most 7 looks, because 27=128≥100. That is binary search, O(log⁡n), and its speed comes entirely from the order. On a shuffled pile, 'too small, so go right' means nothing.

A complete search also says what happens when the target is missing. Linear search can report 'not found' only after checking every item; binary search reports it when the range of possible positions becomes empty. Searching is also different from sorting, even though the two travel together. Sorting rearranges the whole collection; searching leaves it unchanged and answers one question about one target.

Think of it like this. Searching a sorted list is the game 'guess my number from 1 to 100' with 'higher' or 'lower' hints: guessing the middle every time finds any number in 7 guesses or fewer. Take the hints away and the only safe plan is guessing 1, 2, 3 and so on, which is linear search.

Core idea. The best search strategy depends on whether the data is sorted and how large the collection is.


When to Use

Use searching when a program must find a target, report its position, or say whether it exists in a collection. Then choose: if the data is sorted by the value you are looking for, binary search; if not, or if the list is short, linear search. If the task is to put the collection in order, that is Sorting. If you need the largest or smallest value rather than a given target, one pass that tracks the best so far does the job.

Tip. Ask: Must the program find a target value, or say whether it is present, in a collection?

How to Recognize It

Before choosing a search method, pin down what you are looking for, what you are looking in, and whether that collection is sorted.

  1. Is there one target value to find, or to report as missing, in a collection?

    Yes is a searching problem. If the task is to put the whole collection in order instead, that is Sorting.

  2. Is the collection sorted on the value you are searching for?

    Yes allows Binary Search, which halves the range at each step. No leaves Linear Search, unless you sort the data first.

  3. Do you care how many checks the search takes as the collection grows?

    Yes brings in Algorithm Efficiency: linear search grows like O(n) and binary search like O(log⁡n). For a handful of items, either method is fine.

  4. Are you looking for something inside one piece of text, such as a word in a sentence?

    Yes is still searching, with the characters of a String as the collection; Python's in operator and find() do the scanning for you.

Searching vs Sorting vs Linear Search vs Binary Search

Searching and sorting are often taught in the same unit, and linear and binary search are both kinds of searching. Ask whether you are finding one item or reordering all of them, and if finding, whether the data is sorted.

Searching

Meaning
Searching is the task of finding where a target value is in a collection, or reporting that it is absent.
Key test
Output is a position or 'not found', and the data is left unchanged.
Formula
find i with A[i]=t
Example
Finding which seat number in a booking list belongs to Lee.

Sorting

Meaning
Sorting rearranges every item in a collection into a set order, such as smallest to largest.
Key test
The output is the whole collection in a new order.
Example
Putting [9, 2, 7] into the order [2, 7, 9].

Linear Search

Meaning
Linear search walks through the items in order, comparing each with the target, and stops at a match or after the last item.
Key test
Works on unsorted data and needs up to n checks.
Formula
O(n)
Example
Looking for 7 in [4, 9, 7, 1] checks 4, then 9, then 7.

Binary Search

Meaning
Binary search finds a target in sorted data by checking the middle item and discarding the half that cannot contain it.
Key test
Needs sorted data and about log⁡2n checks.
Formula
O(log⁡n)
Example
Finding 23 in [2, 5, 8, 12, 16, 23, 38] checks 12, then 23.

Formula & Notation

Worked Examples

Example 1 — Trace a binary search

Easy

Search the sorted list [3, 8, 12, 19, 24, 31, 40, 52] (indexes 0 to 7) for 31 using binary search. Show each middle checked. How many checks would linear search need for the same target?
Show the steps and the answer
  1. Start with the whole range, indexes 0 to 7. The middle is (0 + 7) ÷ 2 = 3.5, rounded down to 3, which holds 19.

    Checking the middle splits the remaining items into two halves of nearly equal size.

  2. 31 > 19, so the range becomes indexes 4 to 7.

    The list is sorted, so every item at index 3 or below is 19 or less and cannot be 31.

  3. New middle: (4 + 7) ÷ 2 = 5.5, rounded down to 5, which holds 31. Found at index 5.

    One comparison removed half the list, and the second landed on the target.

  4. Linear search checks 3, 8, 12, 19, 24, 31: 6 checks.

    It cannot skip anything, so it reaches index 5 only after looking at every item before it.

Answer: Binary search finds 31 at index 5 after 2 checks; linear search needs 6.

Takeaway: Each binary-search check halves the range, and sorted order is what makes discarding a half safe.

Example 2 — Is sorting first worth it?

Standard

A list of 1,000 usernames is unsorted. Option A: linear search for every lookup. Option B: sort once (about nlog⁡2n≈10,000 comparisons with merge sort), then binary search. Which costs fewer comparisons in the worst case for 1 lookup? For 500 lookups? Roughly where is the break-even?
Show the steps and the answer
  1. One lookup: A needs up to 1,000 comparisons; B needs about 10,000 to sort plus up to 10 to search.

    Binary search needs at most 10 checks because 210=1024≥1000, but it cannot start until the list is sorted.

  2. 500 lookups with A: up to 500 × 1,000 = 500,000 comparisons.

    Linear search pays its full cost again for every lookup.

  3. 500 lookups with B: 10,000 + 500 × 10 = 15,000 comparisons.

    The sorting cost is paid once and then shared by every lookup.

  4. Break-even for k lookups: A costs 1,000k and B costs 10,000 + 10k. At k = 10, A = 10,000 and B = 10,100; at k = 11, A = 11,000 and B = 10,110.

    From 11 lookups on, sorting first is cheaper, and the gap widens with every extra lookup.

Answer: For 1 lookup, plain linear search (1,000 vs about 10,010). For 500 lookups, sort then binary search (about 15,000 vs 500,000). Sorting pays off from about 11 lookups.

Takeaway: Binary search is fast only once the data is sorted. Count the sorting cost too, and sort first when you will search many times.

Example 3 — Find the mistake: binary search on unsorted data

Application

Zoe runs binary search for 7 on [9, 2, 7, 4, 1] (indexes 0 to 4). She writes: "The middle is index 2, which holds 7. Found it, so binary search works on this list." Then she searches the same list for 9 and gets 'not found'. Find the mistake and correct it.
Show the steps and the answer
  1. Trace the search for 9: the middle, index 2, holds 7; 9 > 7, so the search keeps indexes 3 to 4.

    Going right assumes everything on the left is smaller than 7, which is false here: index 0 holds 9.

  2. Continue: index 3 holds 4, 9 > 4, keep index 4; index 4 holds 1, 9 > 1, and the range is now empty. Result: not found.

    Each step threw away a half it assumed was safe, and the half holding 9 was thrown away first.

  3. Explain the first result: finding 7 was luck, because 7 happened to sit in the middle.

    One successful search cannot show a method is correct, but one failure on a target that is present shows it is not.

  4. Fix it: sort first, giving [1, 2, 4, 7, 9], or use linear search on the unsorted list.

    Binary search's choice between left and right is valid only on sorted data.

  5. Re-run on the sorted list: index 2 holds 4, 9 > 4, keep 3 to 4; index 3 holds 7, 9 > 7, keep 4; index 4 holds 9. Found.

    Every discarded half really was too small this time, so the target could not be skipped.

Answer: Binary search needs sorted data. On [1, 2, 4, 7, 9] it finds 9 at index 4 in 3 checks; linear search on the original list finds 9 at index 0 in 1 check.

Takeaway: Before using binary search, confirm that the data is sorted by the value you are searching for.

Where You'll See It

  • Finding a contact in your phone

    Because contacts are sorted alphabetically, you jump near the right letter and zero in (binary-search style) instead of scrolling past every name from the top (linear search).

  • Looking for a specific trading card in a shuffled pile

    If the pile is unsorted you must flip through every card one at a time (linear search) because there's no order to exploit; only sorting them first would let you search faster.

  • Finding a page in a textbook

    Page numbers are in order, so you flip to roughly the middle and decide which half holds your page, halving the search each time like binary search.

Common Mistakes

  1. The slip: Binary search works on any list as long as you pick the middle each time.

    Why it's tempting: The 'check the middle, go left or right' rule sounds purely mechanical.

    Instead: Binary search requires the data to be sorted on the key you're searching. On unsorted data, deciding to go left or right is meaningless and gives wrong answers.

  2. The slip: If a search doesn't find the target, the algorithm can just stop wherever it is.

    Why it's tempting: When the item isn't there, it feels like there's nothing more to handle.

    Instead: A correct search must explicitly handle 'not found' — linear search must finish the whole list, and binary search must stop when the range is empty — and return a clear not-found result.

  3. The slip: Linear search is fine even on big sorted lists since it always works.

    Why it's tempting: It always returns the right answer, so correctness hides the speed cost.

    Instead: On large sorted data, binary search (O(log⁡n)) is orders of magnitude faster than linear search (O(n)); use the sorted structure when it exists.


Mini Practice

Try these on your own. Tap Reveal when you want to check.

  1. Linear search looks for 23 in `[8, 15, 4, 23, 42, 16]`. How many comparisons does it make before finding it?

    Hint: Check items from the front, one at a time.

  2. Binary search looks for 37 in the sorted list `[3, 9, 14, 21, 37, 45, 50]`. List the middle values it checks.

    Hint: Start at the middle item, then keep only the half that could hold 37.

  3. A sorted list has 1,000,000 items. In the worst case, about how many checks does linear search need? About how many does binary search need?

    Hint: Linear search may check every item. How many halvings bring 1,000,000 down to 1?

  4. Linear search looks for 99 in `[5, 12, 7, 30]`. How many comparisons does it make, and what should the function return?

    Hint: What happens after the last item fails to match?

  5. You must find a phone number in a list of 50 contacts stored in random order. Should you use binary search or linear search?

    Hint: What does binary search need to be true about the list?

  6. A student runs binary search for 9 on the unsorted list `[9, 2, 7, 1, 5]` and gets "not found". What went wrong?

    Hint: Trace the first comparison. Which half does it throw away?

Want the full set?

50 practice questions for this concept — free to try, every one with a complete worked solution showing the why, not just the answer.

Frequently Asked Questions

Is it worth sorting data first just so I can use binary search?

It depends on how often you search. Sorting n items takes about nlog⁡nn \log n steps, which is more than one linear search's n. For a single search, just scan. But if you will search the same data thousands of times, sort once and every later search costs about log⁡n\log n, so the sorting pays for itself quickly. Phone contacts and dictionaries stay sorted for this reason.

How does a search engine search billions of pages so fast?

It does not scan the pages when you type. Ahead of time, it builds an index, like the one at the back of a book, listing for each word the pages that contain it. Your query becomes a lookup in that index, which is far faster than reading every page. The hard work moves to building and updating the index, which runs all the time in the background.

What is a hash table, and how can it find things in one step?

A hash table turns each key, such as a username, into a number using a hash function, and uses that number as a position in an array. To look the key up later, you compute the same number and jump straight there, which takes about the same time however many items are stored: O(1)O(1) on average. Python dictionaries work this way. The costs are extra memory and no sorted order.

Learning Path

← Before

ArrayAlgorithm
Searching

You are here

You need Array (items reached by index) and Algorithm (precise steps) first. Searching adds strategies for finding a target, a rule for reporting when it is missing, and the way sorted data changes the cost. Next, Linear Search and Binary Search each get a full lesson, with their loop conditions, edge cases and step counts.

See Also