15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Linear search checks array elements in order, starting at index 0, and compares each one with the target. It returns the first index that matches, or -1 when the scan reaches the end without a match. It needs no sorted input, takes O(n) time in the worst case and uses O(1) extra space.
| Best case time | O(1), target at index 0 |
|---|---|
| Worst case time | O(n), target last or absent |
| Extra space | O(1), no second array |
| Needs sorted input | No |
| Returns | The first matching index, or -1 |
An array of length n has valid indices from 0 through n - 1.
Linear search checks array elements in order, starting at index 0. At each index, it compares that value with the target.
The required result is specific:
-1 when the target does not appear.The array does not need to be sorted. The search only asks whether the current value equals the target, so it works with values in any order.
Use this array and target throughout the lesson:
1A = [7, 3, 9, 3]
2target = 3Show the indices above the values:
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Value | 7 | 3 | 9 | 3 |
There are two occurrences of 3, at indices 1 and 3. Since the required result is the first matching index, the answer must be 1.
Start at index 0. Do not jump to a later position merely because the target appears there too.
The scan changes only one thing: the index being inspected.
Linear search for 3 in [7, 3, 9, 3]: index 0 holds 7, not equal; index 1 holds 3, a match, so return 1. Indices 2 and 3 are never inspected.
Inspect index 0.
1A[0] = 7
27 == 3? No| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Value | 7 | 3 | 9 | 3 |
| Status | checked, not equal | not inspected | not inspected | not inspected |
Since 7 is not the target, move one position right.
Inspect index 1.
1A[1] = 3
23 == 3? Yes| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Value | 7 | 3 | 9 | 3 |
| Status | checked, not equal | matched | not inspected | not inspected |
A match has been found. Return index 1.
Return 1 immediately.
Indices 2 and 3 are not inspected.
1return 1The later 3 at index 3 does not affect the result. Index 1 was encountered first.
Before inspecting an index, look back at the indices already passed.
Before index 0 is inspected, no earlier indices exist.
Before index 1 is inspected in the example, index 0 has already been checked and does not contain the target:
1A[0] = 7, and 7 != 3The scan maintains this rule:
Before inspecting index
i, every index from0throughi - 1has been checked and does not contain the target. Therefore, if a first occurrence exists, it is at indexior later.
The rule is the loop invariant.
Stopping at the first equality comparison is correct because all earlier positions have already been checked and rejected when the algorithm reaches a matching value at index i. The match at i is therefore the first one.
Start at index 0.
For each valid array index:
A[i] with target.i immediately.If the scan reaches index n - 1 and that value is not the target, every valid index has been checked. Return -1.
The algorithm does not use sortedness. It never makes a decision such as “all later values are too large” or “the target cannot appear after this point.” It only tests equality at each position, so both sorted and unsorted arrays follow the same steps.
Inputs
A: an array of values with length ntarget: the value to findReturn value
i such that A[i] == target-1 if no such index existsMutation behavior
firstIndexOf does not change A.11 function firstIndexOf(A, target):
22 n ← length(A)
33
44 for i ← 0 to n - 1:
55 if A[i] == target:
66 return i
77
88 return -1The loop boundary is inclusive: it begins at 0 and can inspect n - 1, the final valid index. For an empty array, n = 0, so there is no valid index to inspect and the loop performs no iterations.
Use the original input:
1A = [7, 3, 9, 3]
2target = 3Call:
1firstIndexOf([7, 3, 9, 3], 3)The array is not modified.
1n ← length(A)1n = 41i ← 0Index 0 is valid because 0 is in the range 0 through 3.
1A[0] == target
27 == 3The comparison is false.
Move to the next index:
1i ← 11A[1] == target
23 == 3The comparison is true.
1return 1The function ends here.
Lines for i = 2 and i = 3 are never reached. Line 8 is also not reached because a match was returned earlier.
We show that firstIndexOf returns the first matching index when one exists, and returns -1 when none exists.
Before the first loop iteration, i = 0.
There are no indices from 0 through i - 1, because that would be indices from 0 through -1. So it is true that every earlier index has been checked and does not contain the target.
The invariant holds before the first inspection.
Assume the invariant holds before inspecting index i.
There are two possible outcomes:
A[i] == target, the function returns i. The returned index contains the target. Also, by the invariant, every earlier index from 0 through i - 1 was checked and did not contain the target. Therefore, i is the first matching index.A[i] != target, index i has now been checked and does not contain the target. Before the next iteration, all indices from 0 through i have been checked and rejected. That is the invariant needed before inspecting index i + 1.Each continuing iteration preserves the invariant.
The loop either returns from line 6 or finishes after inspecting index n - 1.
If it returns from line 6, the equality comparison proves that A[i] equals target. The invariant proves that no earlier index matches, so the returned index is the first matching index.
If the loop finishes, every valid index from 0 through n - 1 has been inspected and rejected. Therefore, no array index contains the target. Returning -1 is correct.
No sortedness assumption is used in the correctness argument. The algorithm works on sorted and unsorted arrays.
Let n be the array length.
The loop performs one equality comparison for each element it inspects.
The target is at index 0.
For example, if the first value equals the target, line 5 succeeds on the first iteration.
11 equality comparisonThe time is O(1).
The target is at the last index, or it is absent.
In either case, the algorithm compares the target with all n array elements.
1n equality comparisonsThe time is O(n).
The iterative scan stores an index i, the length n, and the given target-related variables. It does not create another array or use a growing recursive call stack.
The auxiliary space is O(1).
Incorrect idea:
1for i ← 0 to n - 1:
2 if A[i] == target:
3 return i
4return iSmallest exposing input:
1A = [1, 2]
2target = 3The loop checks indices 0 and 1, then ends. The value of i is 2.
1wrong result = 2But 2 is not a valid array index for this array. The target is absent.
Correction:
1return -1after all elements have been checked.
Incorrect idea:
1result ← -1
2for i ← 0 to n - 1:
3 if A[i] == target:
4 result ← i
5return resultExposing input:
1A = [3, 8, 3]
2target = 3The scan first saves 0, then later overwrites it with 2.
1wrong result = 2The required result is the first matching index, which is 0.
Correction: return immediately when an equality comparison succeeds.
1if A[i] == target:
2 return iIncorrect loop boundary:
1for i ← 1 to n - 1:Exposing input:
1A = [6, 2]
2target = 6The algorithm skips index 0, where the target appears.
1wrong result = -1Correction: initialize the scan at index 0.
1for i ← 0 to n - 1:Array A | target | Required return |
|---|---|---|
[] | 5 | -1 |
[5] | 5 | 0 |
[5] | 2 | -1 |
[2, 2, 2] | 2 | 0 |
[4, 1, 4] | 4 | 0 |
The last case is unsorted. The first 4 is still at index 0, so that is the required result.
Implement this function:
1firstIndexOf(A, target)Contract to satisfy:
i where A[i] == target.-1 if no such index exists.A.0.Tests will include empty arrays, duplicate targets, unsorted arrays, and absent targets.
For terminology and elementary search analysis, consult Algorithms, 4th edition companion site.
1def first_index_of(a, target):
2 for i in range(len(a)):
3 if a[i] == target:
4 return i # stop at the first match
5 return -1
6
7print(first_index_of([7, 3, 9, 3], 3))
8print(first_index_of([1, 2], 3))1public class Main {
2 static int firstIndexOf(int[] a, int target) {
3 for (int i = 0; i < a.length; i++) {
4 if (a[i] == target) return i; // stop at the first match
5 }
6 return -1;
7 }
8
9 public static void main(String[] args) {
10 System.out.println(firstIndexOf(new int[]{7, 3, 9, 3}, 3));
11 System.out.println(firstIndexOf(new int[]{1, 2}, 3));
12 }
13}1#include <iostream>
2#include <vector>
3using namespace std;
4
5int firstIndexOf(const vector<int>& a, int target) {
6 for (int i = 0; i < (int)a.size(); i++) {
7 if (a[i] == target) return i; // stop at the first match
8 }
9 return -1;
10}
11
12int main() {
13 cout << firstIndexOf({7, 3, 9, 3}, 3) << endl;
14 cout << firstIndexOf({1, 2}, 3) << endl;
15}1function firstIndexOf(a, target) {
2 for (let i = 0; i < a.length; i++) {
3 if (a[i] === target) return i; // stop at the first match
4 }
5 return -1;
6}
7
8console.log(firstIndexOf([7, 3, 9, 3], 3));
9console.log(firstIndexOf([1, 2], 3));Linear search checks elements one by one and works on any order, so it costs O(n) comparisons. Binary search halves a sorted range each step and costs O(log n), but it needs sorted input. On unsorted data, linear search is the correct choice.
Yes. It only tests equality at each index and never decides that later values are too large. Sorted and unsorted arrays follow the same steps.
The first index. On [7, 3, 9, 3] with target 3 the answer is 1, and the scan never reads index 3. A version that keeps scanning and overwrites its result returns 3, which breaks the contract.
It returns -1. With n = 0 there is no valid index, so the loop runs zero times and falls through to the final return.
A search algorithm finds where a target sits in a collection, or reports that it is absent. Here that means returning an index, or -1 when the target is missing.