linear search
Finding an item by checking each element in turn from the start until it matches or the list ends.
In more detail
Linear search works on any list, sorted or not, and costs O(n) in the worst case. Python's `in` operator on a list is a linear search. When you search the same data repeatedly, a set, dict or sorted list with binary search is usually far faster.
Example
'zara' in users # checks every name before answering FalseRelated terms
- linear time — Work that grows in direct proportion to the input, written O(n): twice the items, twice the work.
- binary search — Finding a target in sorted data by comparing it with the middle item and throwing away the half where it cannot be.
- membership test — Asking whether a collection contains a given item, written `x in collection` in Python.
Taught in
- Why Complexity Matters In Production — Algorithms & Data Structures for Working Engineers
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Big O, Big Omega And Big Theta — Algorithms & Data Structures for Working Engineers
- What A Hash Function Promises — Algorithms & Data Structures for Working Engineers
- Linked Lists: Nodes, Pointers And Sentinels — Algorithms & Data Structures for Working Engineers
- Searching With Hashes Versus Trees — Algorithms & Data Structures for Working Engineers