Algorithms
Searching (Basics)
Difficulty: Beginner
If your phone's contact list is unsorted and you are looking for Sam, the only option is to read names top to bottom until you find a match or hit the end. That brute-force scan is linear search, and it is the right algorithm in a...
Searching (Basics)
If your phone's contact list is unsorted and you are looking for Sam, the only option is to read names top to bottom until you find a match or hit the end. That brute-force scan is linear search, and it is the right algorithm in a surprising number of situations: small arrays, unsorted data, linked lists, and any case where sorting first would cost more than the search itself.
Searching (Basics) covers linear search and its small family of variations. You will implement the standard O(n) scan in JavaScript and Python, learn the sentinel trick that removes a per-iteration boundary check, and adapt the same template to find the first occurrence, the last occurrence, or the first element matching a condition. The lesson also walks through linear search on linked lists, where you cannot skip ahead by index.
In Arrays & Strings, you saw why arrays support O(1) random access. Searching turns that primitive into a question: how many of those accesses do you need to find a value, and can you do better than reading every one?
That question motivates Binary Search (Intro) next, which exploits sorted order to bring the cost down to O(log n).
Prerequisites:
Arrays & StringsTopics:
What You'll Learn
By the end of this lesson, you will be able to:
Implement linear search in JavaScript and Python and explain why it is O(n).
Apply sentinel linear search to eliminate a boundary check inside the loop.
Find the first and last occurrence of a target in an array.
Search with a predicate (find first element satisfying a condition).
Explain best-case, worst-case, and average-case scenarios for linear search.
Articulate why sorted data enables faster algorithms and motivate binary search.
Why This Matters
01
Searching is the most common operation in programming — nearly every application needs to look up, locate, or verify the existence of data in a collection.
02
Linear search is the simplest algorithm and works on any data (sorted or unsorted), making it the default fallback when no better option is available.
03
Understanding linear search's O(n) cost is what makes the O(log n) improvement of binary search feel dramatic and meaningful.
04
Variants like finding the first occurrence, last occurrence, or conditional search appear constantly in interviews and real-world code.
Key Terms
8 terms you'll encounter in this lesson
Linear search
A search algorithm that checks each element of a collection sequentially until the target is found or all elements have been examined. Also called sequential search.
Sentinel value
A special value appended to the end of an array to guarantee the search will always find a match, eliminating the need for a bounds check inside the loop.
First occurrence
The index of the first (leftmost) element in an array that matches the target value.
Last occurrence
The index of the last (rightmost) element in an array that matches the target value.
Predicate search
Searching for the first element that satisfies a given condition (a boolean function) rather than matching a specific value.
Sequential access
Reading data elements one after another in order, as opposed to random access which jumps directly to a position.
Best case / Worst case
The minimum and maximum number of operations an algorithm performs over all possible inputs of a given size.
Early termination
Stopping a loop as soon as the desired condition is met rather than continuing through remaining elements.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"Linear search is always bad because it is O(n)"
Linear search is O(n), but for small arrays (n < 50) it is often faster than binary search because there is no sorting requirement and the overhead of calculating midpoints is avoided. It is also the only option for unsorted data.
"If the array is sorted, linear search becomes O(log n)"
Sorting the data does not make linear search faster — it still checks elements one by one. You need a different algorithm (binary search) to take advantage of sorted order.
"Linear search always starts from index 0"
Linear search can start from any position and scan in any direction. Searching backward from the end finds the last occurrence directly.
"Sentinel search changes the time complexity"
Sentinel search is still O(n). It improves the constant factor by removing one comparison per iteration (the bounds check), but the growth rate remains linear.