Programming technique · B2.4.2
Linear and binary search
Linear search checks candidates in sequence. Binary search repeatedly discards half of a sorted search interval. Both must be constructed and traced accurately.
Linear search: inspect values in order
Linear search starts at the first position and checks each value until the target is found or no positions remain. It works on unsorted data.
| Target 44 in [12, 25, 31, 44, 57] | Index checked | Value | Result |
|---|---|---|---|
| 1 | 0 | 12 | continue |
| 2 | 1 | 25 | continue |
| 3 | 2 | 31 | continue |
| 4 | 3 | 44 | return 3 |
Binary search: sorted data is a precondition
| Target 57 in [12, 18, 25, 31, 44, 57, 63, 79] | low | high | middle | middle value | Action |
|---|---|---|---|---|---|
| 1 | 0 | 7 | 3 | 31 | 57 is larger → keep indexes 4–7 |
| 2 | 4 | 7 | 5 | 57 | return 5 |
Understand the boundaries
low and high are inclusive
Start at index 0 and length - 1. The current interval includes both boundaries.
Discard the middle too
After a failed middle comparison, use middle + 1 or middle - 1; otherwise the same position may be checked forever.
Index 0 is a valid match
Use -1 for not found so a match at the first position cannot be confused with failure.
Duplicates are allowed
Linear search returns the first match it encounters from the left. This binary search returns a matching index but does not promise the first or last duplicate.
Check your understanding
Answer each question before opening the model answer.
-
Can linear search correctly search an unsorted list?
Reveal model answer
Yes. It checks candidate values directly and does not depend on their order.
-
Why can binary search discard half of the current interval?
Reveal model answer
Because the data is sorted. Comparing the target with the middle value proves that one whole half cannot contain the target.
-
What is wrong with high = values.length for an inclusive high boundary?
Reveal model answer
The final valid index is values.length - 1. Using values.length creates an out-of-range boundary.
-
Which has the slower worst-case growth on large inputs: O(n) linear search or O(log n) binary search?
Reveal model answer
O(n) grows faster. Binary search is generally more scalable for large sorted data, but sorting or maintaining order also has a cost.
Efficiency supports the choice
| Question | Linear search | Binary search |
|---|---|---|
| Sorted data required? | No | Yes |
| Worst-case time | O(n) | O(log n) |
| Auxiliary space, iterative model | O(1) | O(1) |
| Good fit | Small/unsorted/changing data or a one-off search | Large sorted data or repeated searches where order is already maintained |
Challenges Choose one
Choose a challenge that feels appropriate for you. Code heat is only a rough estimate, not a fixed level.
Search Comparison
SelectedConstruct linearSearch and iterative binarySearch methods that return the matching index or -1. Use the supplied sorted data, then add tests for the first value, a middle value, the last value, an absent value and an empty array. Trace at least one successful and one unsuccessful binary search on paper before running the code.
Asset Tag Finder
SelectedStore a set of integer equipment asset tags. Implement both search methods yourself rather than using a built-in search. Count the comparisons made for several targets and compare the worst-case growth of linear and binary search. Explain why binary search is only valid after the tags are kept in sorted order.
Choose the Search
SelectedBuild a small search program around two realistic data sets: one unsorted collection that changes frequently and one sorted collection searched many times. Implement the appropriate search method for each, test found and absent targets, and justify each choice using data order, search frequency, O(n) versus O(log n) worst-case time, and the cost of obtaining or maintaining sorted data.
Selected challenge
This choice is shared with the portfolio setup page.
Plan your solution in handwritten pseudocode
Before opening your IDE or writing any program code, handwrite pseudocode for this challenge on paper.
Not marked complete. If you submit now, the GitHub README will record “No”.
Create your challenge folder
Run this command after planning. It creates the correct empty folder inside your portfolio.
Complete the challenge
Use your handwritten pseudocode as the starting plan, then write and test your solution in the folder created above.
Optional two-level scaffold
Try from your handwritten pseudocode first. Scaffold gives some structure; Scaffold + comments gives stronger guidance. Use only the level you need, and update your pseudocode first if the support changes your plan.
Submit for review
Run this when your program is complete. It creates the README, commits the folder and pushes it. The README records whether you marked the handwritten pseudocode as complete; the paper itself is handed to your teacher separately.