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
Write your first version by hand
Before opening your IDE, write your first attempt at this program on paper using Java. It does not need to be perfect.
TASK_CODE
Not marked complete. Mark it complete when your handwritten code is ready.
Open the challenge
Code Companion Local creates the starter file in the exact managed challenge folder and opens it in your preferred IDE. You do not need to create folders, files or run terminal commands.
Mark your handwritten code complete first.
If you are simply browsing the public course and are not using a class, complete the challenge in any editor you like. Code Companion Local is only needed for the connected classroom workflow.
Complete the challenge
Use your handwritten code as the starting point, then write and test your solution in the challenge workspace. Code Companion Local will ask you to compare the two versions before you submit.
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.