Which search method fits the data?
The key idea
Linear search examines elements one after another and does not require sorted order. Binary search repeatedly narrows a sorted search range by comparing with its middle. Its speed advantage depends on the ordering and access assumptions being satisfied.
Do not apply binary search to an unsorted list and interpret a failed result as proof that the value is absent. The method's precondition is part of its correctness.
Follow a binary-search example
Use the sorted values 3, 7, 11, 18 and 25. Search for 18. The middle value is 11, so the target, if present, must be in the remaining higher part. Compare within that smaller range and locate 18.
Now search for 20. After narrowing the range around 18 and 25, the valid search interval becomes empty. That is the basis for reporting absence; do not return the nearest value unless the task explicitly asks for it.
State the interval convention
An implementation might use an inclusive interval or a half-open interval. Both can work, but the boundary updates must match the chosen convention. Mixing them is a common source of skipped values and non-terminating searches.
When computing an integer midpoint, a form based on low + (high - low) / 2 avoids adding two large non-negative indices directly, provided the interval arithmetic and types are valid.
Compare the workload
| Situation | Useful starting approach | Reason |
|---|---|---|
| One search in a small unsorted collection | Linear scan | No sorting step required |
| Many searches in an already sorted array | Binary search | Repeated range reduction |
| Frequent updates plus searches | Evaluate the full data structure | Maintaining order also has a cost |
| Need the first of several equal values | A defined lower-bound search | Any match may not satisfy the task |
For a sorted array, binary search uses O(log n) comparisons, while a linear scan has O(n) worst-case comparisons. That does not automatically transfer to a structure without efficient indexed access.
Decide what duplicates mean
In 2, 5, 5, 5, 9, the question “is 5 present?” differs from “where is the first 5?” or “how many 5s exist?” Write the required result before selecting or implementing the search.
Test an absent value below the minimum, above the maximum and between two values. Also test empty and single-element collections according to your function's contract.
Your practice task
Create a trace for finding 14 in 4, 8, 14, 21, 30, 42. Record the active range and middle after each step. Then explain why sorting a new unsorted collection for just one lookup may be unnecessary.
The Gammal Tech Algorithms course follows Data Structures. Use that foundation to connect the search method with how your data is stored and updated.
References and course details
Use these references for further study. The examples and exercises in this article are educational; consult the catalogue for course details.