Linear search

As explained in Latency

Linear search is a search algorithm that examines elements sequentially until it finds a target or reaches the end of a collection.

Linear search scans a collection sequentially, stopping when it finds the target or reaches the end. For an array of length n, its worst-case and average-case time complexity are O(n). section 7.2

Sequential array scan

A find function checks each value in order and returns true immediately on a match; otherwise, it returns false after the scan finishes. section 7.2

Figure 7.1 Illustration of algorithmic complexity in big O notation for constant time 𝑂(1), logarithmic time 𝑂(log𝑛), linear time 𝑂(𝑛), and quadratic time 𝑂(𝑛²)

Compare linear growth with constant, logarithmic, and quadratic algorithmic growth as input size increases. section 7.2

How Latency covers it

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.

How it connects

Connects linear search with arrays, Big O notation, hash table lookups, and binary search trees.

liveBookmanning.com

Read Latency on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Grokking Data StructuresLinear 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.
• 

  liveBookmanning.com
  Classic Computer Science Problems in Swift: Essential techniques for practicing programmersA linear search examines elements sequentially in their data-structure order until it finds the sought value or reaches the end.
• 

  liveBookmanning.com
  Clojure: The Essential ReferenceA linear search examines collection elements sequentially until a matching element is found or the collection is exhausted.
• 

  liveBookmanning.com
  Grokking SimplicityA search algorithm that examines elements sequentially until a matching element is found or the collection is exhausted.

Compare how 5 books explain linear search →

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.

This explainer was generated by Manning's knowledge graph from the text of Latency. The section links point to the parts of the book it draws on.