Searching and Sorting: Praxis Computer Science 5652
Linear search works without sorted data; binary search depends on order and efficient access to a middle element.
- Include sorting, updates and repeated queries when comparing the full cost of searching strategies.
- State the required result and assumptions before selecting an algorithm.
On this page21 sections
- Search choice depends on data organization
- Trace binary search with explicit bounds
- Handle absent values and duplicates
- Sorting supports later operations
- Compare sorting algorithms under stated assumptions
- Amortize sorting across repeated searches
- Quick reference
- Define the search result
- Test invariants in binary search
- Sorting keys may need tie-breakers
- Linear search can stop early
- Binary search maintains a shrinking interval
- Include updates in a search plan
- Define ordering before searching
- Search result can be more than a match
- Insertion sort illustrates a tradeoff
- Know what an algorithm promises
- Account for the cost of preparing data
- Check correctness conditions before performance
- Select stable ordering when ties carry meaning
- Trace a partitioning sort at a high level
Search choice depends on data organization
Linear search needs no sorting and works through a sequential scan. Binary search uses ordered data and repeatedly compares the middle element, discarding half of the remaining interval. A search method is only valid when its preconditions are satisfied.
Before choosing, ask whether records are already sorted, whether the structure permits random access, how often queries occur and how often data changes.
Trace binary search with explicit bounds
Use a sorted array and define whether bounds are inclusive or exclusive. For a zero-based inclusive interval low..high, middle can be computed from the bounds, then the next interval is either low..middle-1 or middle+1..high. The interval must shrink each iteration.
Example: search for 22 in [4, 9, 13, 18, 22, 31, 45]. First inspect index 3 (18), then the upper half's middle index 5 (31), then index 4 (22). At each step explain why excluded values cannot be the answer.
Handle absent values and duplicates
A search must define what happens when the target is absent. In binary search, the interval eventually becomes empty, which signals failure under the chosen bound convention. With duplicates, the basic algorithm can find one matching occurrence but may not return the first or last without an added rule.
Test empty arrays, one-element arrays, targets below or above all entries and duplicate runs. Boundary tests expose incorrect updates that ordinary examples can hide.
Sorting supports later operations
Sorting arranges items by a key, such as ID or date. The key must define a useful order, and stability may matter when equal keys retain their prior order. Sorting costs time and may need additional memory, depending on the algorithm.
A teacher sorting student records by surname may want a second sort by first name that preserves surname groups. Stable behavior is relevant only if the task depends on the prior ordering.
Compare sorting algorithms under stated assumptions
Different sorting algorithms have different time, memory and stability properties. Do not attach one complexity claim to every variant with a shared name; implementation and case matter. The course-level exam expects conceptual comparison, not hardware benchmarking.
If a list is nearly sorted or tiny, an algorithm that performs well on that structure may be preferable. If predictable worst-case behavior matters, check the specific algorithm's guarantees. Identify the criterion in the prompt before selecting.
Amortize sorting across repeated searches
Suppose a library receives one lookup in an unsorted 100-record file. Sorting first may not help. If the same catalog is searched thousands of times between updates, sorting or indexing can reduce repeated lookup work. The workload changes the decision.
Include update costs: adding new records may require re-sorting or maintaining an index. A theoretically faster query is not free if preparation and maintenance dominate.
Quick reference
| Method | Precondition | Useful question |
|---|---|---|
| Linear search | None beyond iterable data | Is one scan enough? |
| Binary search | Sorted data and access to midpoint | Can bounds safely halve? |
| Sort then search | Preprocessing and updates considered | How many future queries? |
| Stable sort | Preserves equal-key order | Does prior order matter? |
Define the search result
A search can return a Boolean, an index, a record or the first matching item. The required result changes the algorithm. Basic binary search may return any matching duplicate; a first-match requirement needs a modified boundary rule.
State how an absent target is reported and whether duplicate keys are allowed. These details should be part of the algorithm specification.
Test invariants in binary search
For a closed interval, maintain the invariant that a possible target lies between low and high. After comparing the midpoint, discard only the half that cannot contain the target. Ensure that the interval shrinks.
Try values at both ends and a missing key. These tests catch an update that repeats the same midpoint forever or skips a valid position.
Sorting keys may need tie-breakers
A sort can compare a primary key such as last name and a secondary key such as first name. A stable sort preserves the relative order of equal keys from the input, which can matter in multi-step workflows.
If order among ties does not matter, stability may be unnecessary. Choose based on the output requirement rather than treating stability as universally required.
Linear search can stop early
A sequential scan can return as soon as it finds a matching item. Its best case can be one comparison if the first item matches, while an absent target or last-position target may require scanning the full list.
State the input case when describing its cost. The algorithm needs no sorted order, which can make it sensible for a single lookup.
Binary search maintains a shrinking interval
At each step, compare the middle element and discard the half that cannot contain the target. A correct update must make progress and preserve every candidate location.
For a closed interval, low becomes mid + 1 when the target is greater, or high becomes mid - 1 when it is smaller. When low exceeds high, no candidate remains.
Include updates in a search plan
A list that receives frequent insertions can make maintaining sorted order costly. A database index can speed queries but needs storage and updates.
Compare the total life-cycle workload rather than the one query presented in isolation.
Define ordering before searching
A collection can be sorted by one key and not another. Searching by a different field may not support binary search even when the list appears ordered.
State the sort key and comparison rule. For strings, case, accents or normalization may affect ordering.
Search result can be more than a match
Some tasks need the insertion point, range of duplicates or nearest value, not merely any match. A standard binary search may need modifications to return those results.
Read the required output before selecting pseudocode. A correct index for one duplicate may be wrong for a first-occurrence request.
Insertion sort illustrates a tradeoff
Insertion sort grows a sorted prefix one value at a time. To place the next value, shift larger prefix values right and insert it in the opening. On nearly sorted input it can do little shifting, while reverse order forces many comparisons and moves. Its worst-case growth is quadratic, yet it can be sensible for short or nearly sorted data.
For [3, 5, 7, 4], the first three values are ordered. Inserting 4 shifts 7 and 5, then places 4 after 3. The resulting list is 3, 4, 5, 7. Walking through the state clarifies what a pass means.
Know what an algorithm promises
A stable sorting algorithm preserves the relative order of equal-key records. This matters when records have multiple fields: sorting students by last name can preserve a previous sort by grade if the algorithm is stable. In-place algorithms use little extra storage, though implementations may still require stack space.
Exam questions may ask for a property, a trace or a choice under constraints. Read which one is requested. “Fastest” is incomplete without input size, data condition and memory limits.
Account for the cost of preparing data
Binary search requires sorted data and efficient access to its middle. If a collection must be sorted before one search, the sorting cost may outweigh the saved comparisons. If many searches use the same mostly stable data, the one-time preparation cost can be worthwhile.
Write the whole workload as preparation plus queries. Compare sorting once and then doing repeated logarithmic searches with repeated linear scans. Also account for updates that may invalidate the sorted order. The best method depends on the use pattern, not only the fastest single search.
Check correctness conditions before performance
A fast search is useless if it can silently return the wrong record. Binary search relies on a monotonic ordering that matches the comparison used by the algorithm. Duplicate keys may require a further rule if the task asks for the first or last match.
When reviewing a search, test an empty collection, one element, the first and last positions, a missing target and duplicate values where relevant. These cases expose boundary errors that average examples can hide.
Select stable ordering when ties carry meaning
Suppose student records were first ordered by score and then sorted by last name. A stable second sort preserves the score order among students with the same last name. An unstable algorithm may reorder those ties. If the task requires multiple sort keys, a comparator that explicitly orders both fields can also express the intended result.
This property matters when records carry context beyond their primary key. In an exam question, read whether equal keys and prior order are mentioned. If not, do not assume stability is relevant; if they are, identify the algorithm’s stated guarantee.
Trace a partitioning sort at a high level
Quicksort selects a pivot, partitions values around it and recursively sorts the resulting regions. Its average growth is commonly described as n log n, while poor pivot choices can lead to quadratic work. A balanced partition shrinks both subproblems; a highly unbalanced one makes recursion deep.
When tracing, follow the stated partition convention rather than assuming one implementation. The invariant and pivot placement can differ among versions.
Common questions
Does binary search require sorted input?
Yes, the data must be ordered according to the searched key.
Should I always sort before searching?
No. Include sorting cost, number of queries and data updates.
Does basic binary search find the first duplicate?
Not necessarily; a first-occurrence rule needs an additional condition.