Start with the recap, study the fully worked examples, then use the practice problems to
check your understanding of Searching.
This page combines explanation, solved examples, and follow-up practice so you can move
from recognition to confident problem-solving in CS Thinking.
Concept Recap
The process of locating a specific item or value within a collection of data using a systematic strategy. The two fundamental approaches are linear search (check every element one by one) and binary search (repeatedly halve the search space in sorted data).
Looking for a book on a shelf, a name in a list, a file on your computer.
Read the first worked example with the solution open so the structure is clear.
Try the practice problems before revealing each solution.
Use the related concepts and background knowledge badges if you feel stuck.
What to Focus On
Core idea:The best search strategy depends on whether the data is sorted and how large the collection is.
Common stuck point:Binary search requires sorted data—but is much faster than linear search.
Sense of Study hint:When choosing a search algorithm, first check whether the data is sorted. If unsorted, use linear search. If sorted, use binary search for dramatically faster performance. Always consider the size of the data—for very small collections, the choice barely matters.
Worked Examples
Example 1
medium
Use linear search to find the value 7 in the list [3, 9, 7, 1, 5]. How many comparisons are needed?Linear search for 7: comparisons at indices 0, 1, then match at index 2
Answer
Found at index 2 after 3 comparisons.
First step
1
Step 1: Compare 3 with 7 — no match. Compare 9 with 7 — no match.
See the full worked solution + why-it-works coaching
Setup·Key insight·Why it works·Common pitfall·Connection
Use binary search to find 23 in the sorted list [5, 10, 15, 20, 23, 30, 35]. Show each step.Binary search for 23: found at index 4 after 3 comparisons (step 3: lo=4, hi=4, mid=4)
Example 3
medium
Binary search for 19 in sorted `[2, 5, 8, 11, 14, 17, 19, 23, 27]`. Trace midpoints and count comparisons.Binary search for 19: mid=14 (go right), mid=19 (match) — 2 comparisons
Example 4
medium
Binary search for 8 in `[1, 3, 5, 8, 10, 12, 14]`. Trace the indices examined.Binary search for 8: first midpoint is index 3 (value 8) — found in 1 comparison
Example 5
hard
Binary search for 11 in sorted `[1, 3, 5, 7, 9, 11, 13, 15, 17]` (9 items). Trace mid indices until found and count comparisons.Binary search for 11: mid=9 (go right), mid=13 (go left), mid=11 (match) — 3 comparisons
Example 6
hard
Why does the formula `mid = (low + high) // 2` risk integer overflow in some languages, and what is a safer alternative?
Practice Problems
Try these problems on your own first, then open the solution to compare your method.
Example 1
medium
Can binary search be used on the unsorted list [8, 2, 5, 1, 9]? Why or why not?Unsorted list — binary search cannot be applied correctly
Example 2
hard
A sorted list has 128 elements. In the worst case, about how many comparisons does binary search need, and how does that compare with linear search?
Example 3
easy
Which search checks every element one by one?
Example 4
easy
Which search requires the data to be sorted?
Example 5
easy
Linear search on n items has what worst-case number of comparisons?
Example 6
easy
Binary search on n items takes about how many steps in the worst case?
Example 7
easy
Binary search a sorted array. The middle element equals the target. What happens?
Example 8
easy
If a target is not in the collection, what must a correct search return or signal?
Example 9
easy
For a small unsorted list, which search is simplest and works without preprocessing?
Example 10
easy
In binary search, after comparing to the middle, if the target is larger (in ascending data), which half do you keep?
Example 11
medium
Binary search in sorted `[2,5,8,12,16,23,38,56,72,91]` (10 items) for 23. First midpoint is index 4 (value 16). Which half is searched next?Binary search for 23: first midpoint is index 4 (value 16); 23 > 16 so search the right half
Example 12
medium
In `[2,5,8,12,16,23,38,56,72,91]`, how many comparisons does binary search need to find 23 (mid index 4, then 7, then 5)?Binary search for 23: comparisons at indices 4→7→5, found at index 5 in 3 comparisons
Example 13
medium
To search a list 1000 times, sorting once costs setup. When is sorting first then using binary search worth it?
Example 14
medium
Worst case, how many comparisons does binary search need on 1000 sorted items?
Example 15
medium
Why does binary search give WRONG results on unsorted data?
Example 16
medium
Linear search finds the target at position 3 (0-indexed) in a 10-element list. How many comparisons were made?
Example 17
medium
A phone book is sorted by name. To find 'Smith', which search is far more efficient than scanning page by page?
Example 18
challenge
Binary search in `[1,3,5,7,9,11,13]` (7 items) for 4 (which is absent). Trace the midpoints until the range is empty. How many comparisons before declaring not found?Binary search for 4 (absent): 3 comparisons — mid=7, then mid=3, then mid=5; range empties → not found
Example 19
challenge
A buggy binary search uses `low <= high` but never updates `low`/`high` correctly, so the range never shrinks. What failure results?
Example 20
challenge
You must search an UNSORTED array of n once for one value. Is it worth sorting first (O(nlogn)) to use binary search (O(logn))?
Example 21
medium
Linear search a 6-element list for a value that is absent. How many comparisons are made?
Example 22
medium
Binary search needs the data sorted. If you receive unsorted data and must search it many times, what is the right preprocessing step?
Example 23
easy
Linear search for 9 in `[2, 4, 9, 7, 1]`. How many comparisons until found?Linear search for 9: compare 2 (no), compare 4 (no), compare 9 (match) — 3 comparisons
Example 24
easy
Binary search needs the data to be in what order?
Example 25
easy
Linear search on a list of 50 items for a target NOT in the list. How many comparisons in the worst case?
Example 26
easy
Sorted list `[1, 3, 5, 7, 9]`. Binary search for 5. Which index is checked first?Binary search for 5: first midpoint is index 2 (value 5) — found in 1 comparison
Example 27
easy
A correct search function returns what when the target is not found?
Example 28
medium
A sorted array has 1,048,576 elements. Worst-case binary search comparisons?
Example 29
medium
Why does binary search fail correctness on `[3, 1, 4, 1, 5, 9, 2, 6]` when looking for 9?Unsorted data — binary search cannot safely discard a half and may miss the target
Example 30
medium
Linear search for 6 in `[1, 2, 6, 6, 6]` returning the first match index. What is the result?Linear search for first 6: compare 1 (no), compare 2 (no), compare 6 at index 2 (match) — return index 2
Example 31
medium
If you must search the SAME sorted data many times, which strategy is faster overall, linear or binary search?
Example 32
medium
Binary search worst-case comparisons on 100,000 sorted items (round up)?
Example 33
medium
Linear search a list of 12 items; the target is at index 0. How many comparisons?
Example 34
medium
Linear search for 7 in `[3, 7, 7, 7]`, returning the LAST occurrence's index. What does it return?Linear search for last 7: scan all elements, keep updating last-match index; return index 3
Example 35
medium
Binary search a sorted ascending list. The middle is smaller than the target. Which half do you keep?
Example 36
medium
You sort an unsorted list of n items once (cost ∼nlogn) and then search it k times with binary search (each ∼logn). When is this beat by k linear searches?
Example 37
hard
Linear search a list of n items where every element equals the target. What is the worst-case index returned if the function returns the first match?
Example 38
hard
Binary search for 4 (not in list) in sorted `[1, 3, 5, 7, 9]`. How many comparisons before it concludes 'not found'?Binary search for 4 (absent from [1,3,5,7,9]): 3 comparisons — mid=5, mid=1, mid=3; range empties → not found
Example 39
hard
A buggy binary search computes `mid = (low + high) // 2` but never updates `low = mid + 1` or `high = mid - 1`. What failure occurs?
Example 40
challenge
You have a sorted list of 1,000,000,000 (one billion) items. Approximately how many comparisons does binary search need in the worst case?