Linear Search — Implement linear search over arrays/lists - Java

SECTION 1

Historical Context & Motivation

Searching for information is one of the oldest and most fundamental tasks in computing. Before computers existed, people performed linear search every day without even knowing it — flipping through a phone book page by page, scanning a grocery list item by item, or looking through a deck of cards one at a time. When early computers arrived in the 1940s and 1950s, programmers needed a way to locate specific pieces of data stored in memory, and the most natural approach was to check each location sequentially.

As data sets grew larger, the need for faster searching techniques led to innovations like binary search and hash tables. However, linear search remains a foundational algorithm that every programmer must understand. It serves as the baseline against which all other search algorithms are measured, and it is often the only option when data is unsorted or when the collection is small.

1945 • Early Stored-Program Computers

The first general-purpose electronic computers, like ENIAC, stored data in sequential memory. Searching through this data naturally meant scanning it one element at a time — the earliest form of linear search in computing.

1946 • Von Neumann's Architecture

John von Neumann's stored-program concept placed instructions and data in the same linear memory space. Sequential access patterns, including linear search, became a core programming technique.

1962 • Knuth Begins 'The Art of Computer Programming'

Donald Knuth began writing his seminal textbook series, which formalized the analysis of searching algorithms. Volume 3, 'Sorting and Searching,' rigorously analyzed linear search as the simplest sequential search method.

1995 • Java Released

Sun Microsystems released Java 1.0, providing built-in array and collection types. Java's Arrays and Collections classes would eventually offer utility methods, but understanding how linear search works under the hood remains essential.

The central question linear search answers is straightforward: "Does a specific value exist in this collection, and if so, where is it?" While more sophisticated algorithms can answer this question faster under certain conditions, linear search works in every situation — no sorting required, no special data structure needed. Understanding it is the first step toward mastering all search algorithms.

SECTION 2

Core Principles & Definitions

Linear search (also called sequential search) is an algorithm that examines each element in a collection one at a time, starting from the first element and moving toward the last. At every position, it compares the current element to the target value — the value you are searching for. If a match is found, the algorithm returns the index of that element. If the entire collection is traversed without finding a match, the algorithm reports that the target is not present.

Sequential Traversal

The algorithm visits elements in order from index 0 to index n − 1. It does not skip any element or jump ahead, ensuring that every item is inspected.

Comparison-Based

At each step, the current element is compared to the target using an equality check. In Java, this is typically done with == for primitives or .equals() for objects.

Early Termination

As soon as the target is found, the algorithm stops and returns the current index. This means it doesn't always scan the entire array — it can finish early if the target appears near the beginning.

No Preconditions

Unlike binary search, linear search does not require the array to be sorted. It works on any array or list regardless of element order, making it universally applicable.

Returns −1 on Failure

By convention, if the target is not found, the method returns −1. Since valid array indices start at 0, returning −1 clearly signals that the element does not exist in the collection.

✦

KEY TAKEAWAY

Think of linear search like looking for your friend in a movie theater. You start at the first row, scan every seat, and move to the next row. You don't skip any seat, and you stop the moment you spot them. If you reach the last row without finding them, you conclude they aren't there. That's exactly what linear search does with an array.

SECTION 3

Visual Explanation

The diagram below illustrates how linear search operates on an array of seven integers. The algorithm is looking for the target value 42. Each row shows a step of the algorithm. The blue highlighted cell indicates the element currently being compared to the target. When the target is found at index 4, the algorithm stops and returns that index.

The algorithm starts at index 0 and checks each element. After five comparisons, it finds 42 at index 4 and immediately returns. Elements at indices 5 and 6 are never inspected because of early termination.

Notice how the algorithm does not look ahead or make any assumptions about where the target might be. It strictly follows the sequence: check index 0, then index 1, then index 2, and so on. This is why it is called a sequential or linear search — the pattern of access is a straight line through the data.

SECTION 4

Time Complexity & Mathematical Framework

To evaluate an algorithm's efficiency, computer scientists use Big-O notation, which describes how the number of operations grows as the input size increases. For linear search, the input size is n, the number of elements in the array. We analyze three scenarios: the best case, worst case, and average case.

BEST CASE

T(n) = O(1)

The target is the first element of the array. Only one comparison is needed, so the running time is constant regardless of the array's size.

WORST CASE

T(n) = O(n)

The target is the last element or is not present at all. The algorithm must inspect every element, so the number of comparisons equals n, the array length.

AVERAGE CASE

T(n) = O(n/2) = O(n)

On average, if the target is equally likely to be at any position, the algorithm checks about half the elements. Since Big-O ignores constant factors, n/2 simplifies to O(n). The variable n represents the total number of elements in the array.

SPACE COMPLEXITY

S(n) = O(1)

Linear search uses a fixed amount of extra memory — just one loop variable and one variable for the target. It does not create any additional data structures. This makes it an in-place algorithm.

The key insight is that linear search's running time grows directly with the size of the input. If you double the array size from 100 to 200 elements, the worst-case number of comparisons also doubles. This linear relationship between input size and time is what gives the algorithm its name.

SECTION 5

Java Implementation & Code Walkthrough

Now let's translate the algorithm into Java code. Below is a complete implementation of linear search for an integer array, followed by a visual breakdown of how each part of the code maps to the algorithm's logic.

The annotated code shows the five key parts of the implementation: ① the method takes an array and a target, ② a for loop iterates through each index, ③ an if statement compares each element to the target, ④ finding a match triggers an immediate return, and ⑤ reaching the end of the loop means the target was not found.

A few important details about this implementation. First, the method is declared static so it can be called without creating an object — this is common for utility methods. Second, we use == for comparison because we are working with int primitives. If you were searching an array of String objects, you would need to use .equals() instead, since == compares object references rather than content.

💡

String Search Variation

For searching an array of Strings, change the comparison line to: if (arr[i].equals(target)). Using == on Strings checks whether two references point to the same object in memory, which is almost never what you want. The .equals() method checks whether the actual characters match.

SECTION 6

Worked Example

Let's trace through a complete example to solidify our understanding. We will search for a student's name in an array of Strings and track exactly what happens at each step.

Finding "Diana" in a String Array

1
Step 1 — Define the Array and Target

We have the array String[] names = {"Alice", "Bob", "Carlos", "Diana", "Eve"}; and our target is "Diana". The array has 5 elements, so our loop will run from index 0 to index 4 at most.

n = 5, target = "Diana"
2
Step 2 — Iteration i = 0

We check names[0].equals("Diana"). The element at index 0 is "Alice". Since "Alice" does not equal "Diana", the condition is false. We move to the next iteration.

"Alice".equals("Diana") → false
3
Step 3 — Iteration i = 1

We check names[1].equals("Diana"). The element at index 1 is "Bob". This is still not a match, so we continue.

"Bob".equals("Diana") → false
4
Step 4 — Iteration i = 2

We check names[2].equals("Diana"). The element at index 2 is "Carlos". Still no match.

"Carlos".equals("Diana") → false
5
Step 5 — Iteration i = 3 (Match Found!)

We check names[3].equals("Diana"). The element at index 3 is "Diana" — a perfect match! The if condition evaluates to true, so we immediately execute return 3;. The method exits without ever checking index 4 ("Eve").

"Diana".equals("Diana") → true → return 3
6
Step 6 — Interpret the Result

The method returned 3, meaning "Diana" was found at index 3. The total number of comparisons was 4 (indices 0 through 3). Had "Diana" not been in the array, the loop would have completed all 5 iterations and the method would have returned −1.

Result: index 3, comparisons made: 4 out of 5

SECTION 7

Strengths, Limitations & Comparisons

Linear search is often the right tool for the job in certain situations, but it also has clear limitations when data sets grow large. Understanding when to use it — and when to reach for something faster — is an important skill in algorithm design.

Aspect	Strengths	Limitations
Simplicity	Easy to understand, implement, and debug. Great for beginners and quick prototyping.	No cleverness — it cannot leverage any structure in the data to run faster.
Preconditions	Works on unsorted data, linked lists, and any iterable collection. No preprocessing needed.	Cannot take advantage of sorted data the way binary search can.
Speed	Fast for small arrays (under ~100 elements). Minimal overhead from simple loop structure.	O(n) worst case becomes impractical for millions of elements. Binary search achieves O(log n).
Memory	O(1) space — uses only a loop counter and the target. No additional data structures required.	No limitation here — linear search is memory-optimal.
Multiple results	Easily modified to find all occurrences of a target, not just the first.	Finding all occurrences always requires a full scan of the array.

Strengths and limitations of linear search

🎯

WHEN TO USE LINEAR SEARCH

Use linear search when the data is unsorted, when the array is small, or when you only need to search once. If you need to search the same large, sorted dataset many times, invest in binary search or a hash-based structure. Think of it this way: if you only need to find one phone number, flipping through the entire phone book is fine. But if you look up numbers every day, you'd want an alphabetized index.

SECTION 8

Connection to Binary Search & Advanced Algorithms

Linear search is the foundation upon which you can appreciate more advanced search algorithms. The most important next step is binary search, which requires a sorted array but dramatically reduces the number of comparisons by cutting the search space in half with each step.

Feature	Linear Search	Binary Search
Time complexity	O(n)	O(log n)
Requires sorted data?	No	Yes
Comparisons for 1,000,000 elements	Up to 1,000,000	At most 20
Implementation difficulty	Very simple	Moderate (off-by-one errors common)
Works on linked lists?	Yes, efficiently	Not efficiently (no random access)

Linear Search vs. Binary Search

Beyond binary search, you will eventually encounter hash tables (Java's HashMap), which can find elements in O(1) average time by computing a hash code. There are also tree-based searches (like Java's TreeMap) that keep data sorted and allow O(log n) lookups. Each of these builds on the idea that searching is one of the most common operations in programming, and optimizing it yields enormous performance gains.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain why linear search does not require the array to be sorted. What property of the algorithm makes sorting unnecessary?

Show answer

Linear search visits every element from index 0 to the end of the array. Because it checks each element exactly once in sequence, it does not need to make any assumptions about the order of the data. The algorithm's correctness depends only on the fact that it inspects every position — not on any ordering property. Sorting is only necessary for algorithms like binary search that skip elements based on comparisons with values at specific positions.

Question 2: BASIC CALCULATION

Given the array {5, 12, 8, 3, 17, 9} and target value 17, how many comparisons does linear search perform before finding the target? What index does the method return?

Show answer

The algorithm compares the target (17) with each element starting at index 0. It checks 5, then 12, then 8, then 3, then 17. When it reaches index 4, it finds a match. That means it performed 5 comparisons total (at indices 0 through 4). The method returns the value 4, which is the index where 17 is located. Elements at index 5 (the value 9) are never checked because the method exits early upon finding the match.

Question 3: INTERMEDIATE

Modify the linear search method so that instead of returning the index of the first occurrence, it returns the count of how many times the target appears in the array. Write the Java method signature and body.

Show answer

Instead of returning early when a match is found, you keep a counter and increment it for every match. The method would be:

public static int countOccurrences(int[] arr, int target) { int count = 0; for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { count++; } } return count; }

The key difference is removing the early return. The loop must always run through the entire array to count all occurrences, making this always O(n) with no best-case shortcut. The method returns 0 if the target is never found, which naturally handles the "not present" case.

Question 4: APPLIED

A teacher stores 30 student test scores in an array. She wants to find which students scored below 60 (failing grade) and print their indices. Write a Java method findFailingIndices(int[] scores, int passingMark) that uses a linear search approach to print all indices where the score is below the passing mark.

Show answer

This is a variation of linear search where instead of checking equality to a target, you check a condition (less than the passing mark). The method:

public static void findFailingIndices(int[] scores, int passingMark) { for (int i = 0; i < scores.length; i++) { if (scores[i] < passingMark) { System.out.println("Student at index " + i + " scored " + scores[i]); } } }

This demonstrates that linear search is a general pattern — traverse sequentially and apply a condition. The time complexity is O(n) since every score must be checked. You could also collect the indices into an ArrayList and return it instead of printing directly.

Question 5: CRITICAL THINKING

Imagine you have an array of 10,000 elements and you need to search for 500 different target values. Would you use linear search for each lookup, or would you sort the array first and use binary search? Justify your answer by comparing the total number of operations for each approach.

Show answer

With linear search, each lookup takes up to 10,000 comparisons in the worst case. For 500 lookups, that is up to 500 × 10,000 = 5,000,000 comparisons. With the sort-then-binary-search approach, sorting takes roughly n × log₂(n) ≈ 10,000 × 13.3 ≈ 133,000 operations. Each binary search then takes at most log₂(10,000) ≈ 14 comparisons, so 500 lookups cost 500 × 14 = 7,000. The total is about 133,000 + 7,000 = 140,000 operations. Sorting first and using binary search is approximately 35 times faster. The lesson here is that when you need to search the same dataset many times, the upfront cost of sorting pays for itself quickly. Linear search remains better only when the number of lookups is very small (fewer than about 13 in this case).

SUMMARY

Lesson Summary

Summary

Linear search is the simplest searching algorithm: it starts at the beginning of an array and checks each element one by one until it finds the target value or reaches the end. It requires no sorting or preprocessing and works on any collection type. In Java, you implement it with a for loop and an if statement using == for primitives or .equals() for objects. The method returns the index of the match or −1 if the target is not found.

The time complexity is O(1) best case (target at index 0) and O(n) worst case (target absent or at the end), with O(1) space complexity. For large, sorted datasets searched repeatedly, binary search (O(log n)) is far more efficient. Linear search remains the go-to choice for small or unsorted collections and serves as the baseline for understanding all other search algorithms.