Linear search
Linear search is a search technique that examines candidates sequentially until it finds a match or exhausts the collection.
Grokking Data Structures
Linear search examines the elements of a sequence one by one, typically from one end to the other, until the target is found or the sequence is exhausted.
- How it is used
- Supports searching arrays and linked lists when elements are examined sequentially until a match or endpoint appears.
- How deep it goes
- Explains scan behavior, sorted-array early termination, linked-list constraints, implementations, and O(n) analysis before contrasting binary search.
- Examples
- Uses sorted-array searches for targets 8 and 9, plus array and linked-list search implementations.
- What you can do after
- Build it from scratch by scanning arrays or linked lists, returning a match appropriately, and recognizing O(n) performance.
Classic Computer Science Problems in Swift: Essential techniques for practicing programmers
A linear search examines elements sequentially in their data-structure order until it finds the sought value or reaches the end.
- How it is used
- Uses sequential inspection to determine whether a value occurs in an unsorted or otherwise directly traversable collection.
- How deep it goes
- Defines the scan, implements it for codons and generic Swift collections, and identifies O(n) worst-case work.
- Examples
- Uses a gene of codons, the target codon ACG, a generic Swift function, and million-element timing exercises.
- What you can do after
- Build it from scratch for codons or generic Equatable arrays, then compare its timing with binary search.
Clojure: The Essential Reference
A linear search examines collection elements sequentially until a matching element is found or the collection is exhausted.
- How it is used
- Clarifies how to perform explicit element scans instead of misusing contains? on vectors.
- How deep it goes
- Defines sequential scanning and contrasts some, .contains, and contains? without developing implementation internals.
- Examples
- Uses some on a vector, an equality predicate for nil, vector index checks, and Java .contains calls.
- What you can do after
- Apply it via some or .contains when selecting an explicit element or substring scan.
Read how Clojure: The Essential Reference explains linear search →
Grokking Simplicity
A search algorithm that examines elements sequentially until a matching element is found or the collection is exhausted.
- How it is used
- Uses sequential array search to separate item lookup from cart operations and expose opportunities for reuse.
- How deep it goes
- Works through extraction, return values, layer structure, and reuse, then defers a more general loop version.
- Examples
- Uses shopping-cart lookup, item removal, membership testing, and price updates as concrete search clients.
- What you can do after
- Apply it via a reusable indexOfItem() function that returns an index or null for cart-based operations.
Latency
Linear search is a search algorithm that examines elements sequentially until it finds a target or reaches the end of a collection.
- How it is used
- Uses sequential scanning to find a target in an array and frame runtime growth in algorithmic complexity.
- How deep it goes
- Defines scanning behavior and average and worst-case O(n), but stops short of detailed implementation analysis.
- Examples
- Uses array target search, active orders as input-size intuition, and a sequential find function.
- What you can do after
- Apply it by scanning a collection and estimating average and worst-case search growth.
Related concepts
- binary searchcontrasts with · Binary search is an algorithm that locates a target or boundary in an ordered collection by repeatedly comparing with a midpoint and halving the remaining search range.
- linear time complexitymeasured by · Linear time complexity is an asymptotic running-time growth rate proportional to input size, or to the combined sizes of multiple inputs, up to a constant factor.
- findimplemented by · A find operation searches a collection for the first element or entry matching a value or predicate and returns it, or indicates that no match exists.
- containsimplemented by · Contains is a membership-query operation that reports whether a specified value, key, element, or substring occurs in a container or collection.
- k-d treecontrasts with · A k-d tree is a binary space-partitioning tree that organizes points in multidimensional space by recursively comparing coordinate dimensions.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.