Where it runs
1. The problem
So far you have done things with arrays: added them up, moved a window, built prefix sums. Now the simplest question of all: is a value in the list, and if it is, where?
If the list has no order at all, there is no shortcut. The item you want could be anywhere. The one safe move is to look at the cells one by one until you find it or the list runs out.
You have a list of 500 user records in the order the users signed up. It is not sorted by any field. Someone asks for the user with id 4092. You have to walk the list and check the id of each record until one matches.
2. In plain words
Back to the 500 users. You need id 4092. You look at the first record: id 17, not it. The second: id 3301, not it. And so on, one at a time. If the record with id 4092 is the 20th, you stop at the 20th.
If there is no such user at all, you find out only at the very end, after you have checked all 500 records. You can't say "no" earlier: any record you haven't checked could be the one.
3. The idea
Walk the list from the first cell to the last. In each cell, compare its value with the one you are looking for. As soon as they match, stop and return that position. That is the answer.
If you reach the end with no match, the value is not in the list. Return -1, which means "not found". Return the position of the first match: a value can appear more than once, and usually the first one is the one people want.
Trace it on [4, 2, 9, 7, 1, 5], looking for 7.
- Cell 0 holds 4, not it.
- Cell 1 holds 2, not it.
- Cell 2 holds 9, not it.
- Cell 3 holds 7, a match. Return 3.
That took four checks. Looking for 8 instead, you would check all six cells and return -1.
4. What it costs
Time is O(n). In the worst case the item is last or missing, and you check all n cells. On average you check about half. Either way, the work grows with the length of the list.
Memory is O(1). You keep one loop counter and nothing that grows with the input.
This is the price of an unordered list. The next lessons work with sorted data. In a sorted list, binary search finds an item in about log n checks instead of n. Scanning is the plain starting point that all other methods are compared with.
5. Where this shows up
Array.prototype.indexOf, find and includes in JavaScript, and the in operator on a Python list. Finding the first matching line in an unsorted log or buffer. Finding a setting in a short list, where sorting would cost more than it saves. Any pass of the form "find the first element that meets condition X" over data with no useful order.
linearSearch([7, 3, 9, 4, 8, 2], 8)Find the index of 8. The array is not sorted, so the only way is to check the numbers one by one from the start.
Bars: the sorted numbers. Both lanes look for one near the end.
One operation is one comparison with the target. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(n)O(log n)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- unsorted array
- check every element
- no order guarantee
- find first/any match
- small n or one-time scan
Looks similar, isn't
- Binary search (array)
Binary search needs sorted data and pays log n. A scan reads anything, in any order.
- Hash set / map
A map answers instantly but has to be built first. For a single lookup the scan is cheaper.
- Two pointers (same direction)
That pair rewrites the array while it scans. A search only ever reads.
- Sliding window (variable)
A window carries a description of a live span. A scan carries at most the best seen so far.
- Elementary sorts (selection, bubble, insertion)
Sorting first costs O(n log n) and pays off across many searches. One lookup does not repay it.
n up to roughly 1e7 gives O(n) time and O(1) space. Bigger, or repeated, wants a real structure.
On LeetCode
Easy problems that ask for the first item, index or place that matches a condition, in data with no useful order. Scan from the start, stop at the first match, and return -1 when there is none.
The lesson's scan with another check, i % 10 == nums[i], and -1 when nothing matches.
Scan the words in order and return the first one that reads the same backwards.
Try every start position from the left and return the first one where needle matches.
Scan once and stop at the first place where three odd numbers stand in a row.
Your task (Tier 1)
Write the function linearSearch(nums, target).
Go through the list from the start. Return the position of the first number that equals target. If no number matches, return -1.
- Input:
nums, a list of numbers in any order, andtarget, the number you look for. Example:[4, 2, 9, 7, 1, 5]with target7. - Return: the position of the first match, or
-1if there is no match.
Steps:
- Go through the list from left to right, one position at a time.
- If the number at this position equals
target, return this position right away. - If you reach the end with no match, return
-1.
Done when all tests pass:
[4, 2, 9, 7, 1, 5], target7->3(a match in the middle)[5, 1, 2], target5->0(the first number)[1, 2, 3], target3->2(the last number)[3, 7, 3, 7], target7->1(return the first match)[1, 2, 3], target9->-1(the number is not in the list)[], target5->-1(empty list, must not crash)[8], target8->0(one number, a match)[8], target3->-1(one number, no match)
Practice
linearSearch
linearSearch(nums, target) -> index (0-based) of first match, or -1
export function linearSearch(nums, target) {
// Your code here. The task is described in the box above the editor.
}
Running as a guest
The tests run right here, no account needed. Your code is kept in this browser only. A free account keeps it on every device, marks the step done and shows where you are in the course.
Hint ladder
Stuck? Reveal one rung at a time, but try it yourself first.