Linear Search
Algorithm · Starter
Step through it: Modified Binary Search pattern
target = 23
Step 1 of 6
Goal: find 23 in this sorted list. Checking one number at a time could take 7 looks, and a million numbers would take up to a million. Because the list is sorted, we can do far better.
Step 2 of 6
Look at the middle number first. The middle of positions 0 to 6 is position 3, which holds 12.
Step 3 of 6
12 is smaller than 23, and the list is sorted, so 23 cannot be at or before 12. Throw away that whole half. Only positions 4 to 6 are left.
Step 4 of 6
Do the same thing on what is left. The middle of positions 4 to 6 is position 5, which holds 23. Found it.
Step 5 of 6
Two looks instead of up to seven. Every look halves what is left, so a million numbers need only about 20 looks. Halving the search area each time is called binary search.
Step 6 of 6
Your turn. Pick a target and press Next to watch each look. Try 7: it is not in the list.
Complexity
Time Complexity
O(n) - since in worst case we're checking each element
exactly once.
In computer science, linear search or sequential search is a
method for finding a target value within a list. It sequentially
checks each element of the list for the target value until a
match is found or until all the elements have been searched.
Linear search runs in at worst linear time and makes at most n
comparisons, where n is the length of the list.
Code
import Comparator from '../../../utils/comparator/Comparator';
/**
* Linear search implementation.
*
* @param {*[]} array
* @param {*} seekElement
* @param {function(a, b)} [comparatorCallback]
* @return {number[]}
*/
export default function linearSearch(array, seekElement, comparatorCallback) {
const comparator = new Comparator(comparatorCallback);
const foundIndices = [];
array.forEach((element, index) => {
if (comparator.equal(element, seekElement)) {
foundIndices.push(index);
}
});
return foundIndices;
}References
Practice
Modified Binary Search
- Binary SearchEasy
- Search Insert PositionEasy
- Sqrt(x)Easy
- First Bad VersionEasy
- Valid Perfect SquareEasy
- Arranging CoinsEasy
- Search in Rotated Sorted ArrayMedium
- Find Minimum in Rotated Sorted ArrayMedium
- Find First and Last Position of Element in Sorted ArrayMedium
- Find Peak ElementMedium
- Search a 2D MatrixMedium
- Koko Eating BananasMedium
- Capacity To Ship Packages Within D DaysMedium
- Time Based Key-Value StoreMedium
- Single Element in a Sorted ArrayMedium
- Minimum Number of Days to Make m BouquetsMedium
- Median of Two Sorted ArraysHard
- Split Array Largest SumHard
- Find Minimum in Rotated Sorted Array IIHard
Spotted a mistake or something unclear? Report it on GitHub.