Checking Every Element One at a Time Until the Target Appears

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 9.1 Free with a free account

Checking Every Element One at a Time Until the Target Appears

Data Structures and Algorithms · Chapter 9: SearchingSection 9.1 · lesson 35 of 8710 min · free with a free account

← Self-Calling Techniques for Complex StructuresNext lesson: Binary Search →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Sequential search on arrays and linked lists, its traps, and its cost.

  • Implement sequential search on an array and on a linked list in Java
  • Signal and check a not-found result safely
  • Explain the sentinel technique and its risks
  • Analyze the best, worst, and average cost of sequential search

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,511 words). Read along, or search it.

Opening Question

One Paper in an Unsorted Pile

A stack of unsorted exam papers lands on your desk, and you need the one with Dee's name on it. How many papers will you have to check? With no order to use, there's no clever trick. Check the first paper, then the second, until it turns up, or the pile runs out. That patient method is sequential search, also called linear search. It works on any collection, and every faster search is measured against it. By the end, you'll know what it costs, and when it's the right tool.

Worked Example

Sequential Search on an Array

On an array, start at index zero. Compare each element with the target, the value you want, and stop at a match, or at the end. A match returns its index straight away. That's early exit. If the loop finishes, the target isn't there, so the method returns minus one. The counter is only there to count the work. Run it on eight numbers, for four targets. Forty-two is in the first cell: one comparison. Twenty-three takes four. And four, in the last cell, takes eight. Fifty isn't there, and it also costs eight. Proving that a value is missing means checking every cell.

Variations

Counting, Last Match, and Conditions

Change a few lines, and the same loop answers other questions. Counting occurrences can't stop early, because every cell matters. Finding the last occurrence scans from the right end. And finding the first element that meets a condition only changes the test. On five, three, five, eight, five: five appears three times, and last at index four. The first value above six is at index three, and nine isn't there.

Quick Check

Less Than or Equal Goes Out of Bounds

Quick check. In this version, the loop runs while i is less than or equal to the array's length. It searches five, six, seven, for nine. What happens? Pause, and predict. It throws an exception. Nine isn't in the three cells, so i reaches three, and a of three doesn't exist. Java stops with Index 3 out of bounds for length 3. The loop never gets to return minus one. Valid positions run from zero to the length minus one, so the test must be, i less than a dot length.

Linked Lists

Walking a Linked List by Links

A linked list has no index arithmetic. To reach the fourth node, you follow links from the head, one at a time. So the search stands on the head, compares, steps to cur dot next, and repeats, until it finds the target, or falls off the end at null. Names are objects, so the test uses equals. And the search counts its steps as it goes. On the list Ava, Ben, Cy, Dee, Eli: Dee is found at index three, after four steps. Zed takes all five, then null. Ava is found at once, and Eli last. An empty list returns minus one after zero steps, because the loop body never runs.

Comparison

Index Steps Versus Link Steps

The two searches differ only in how they move. An array jumps to any position in one step. A list must follow i links to get there. The array steps with i plus plus, and the list with cur equals cur dot next. One stops at the array's length, and the other at null. Either way, the cost grows in proportion to n, the number of elements.

Common Mistake

Calling Get Inside a Loop

Now a trap. It's tempting to search a linked list with an index loop, calling get of i, because it looks like the array version. But each get starts again at the head, and follows i links. That's a hidden loop, inside the loop. On 10,000 nodes, with a target that isn't there, the index loop follows 49,995,000 links. The walking loop takes 10,000 steps. So on a linked list, always walk, with cur equals cur dot next.

Key Idea

Early Exit Saves Work

Early exit is what made twenty-three cheap. A version that remembers the first match, but keeps scanning, makes eight comparisons instead of four. For an absent target, both make eight. Early exit never changes the answer. It only saves work when the target appears before the end.

Design Choice

Signaling Not Found

Minus one is a safe signal for not found, because a real index runs from zero to n minus one. Java's own index of methods use it too. Return null when the result is an object or a node. Return true or false when only, is it there, matters. And throw an exception when a missing value means the program has a bug. Whatever the signal, the caller must check it.

Common Mistake

Using Minus One as an Index

Here's a caller that ignores the signal. It searches five, six, seven, for ninety-nine, and uses the answer straight away, as an index. Java stops with Index -1 out of bounds for length 3. The fix is one line: check for minus one before using the result. Run it again: not found, and no crash.

Common Mistake

Double Equals Versus Equals

Strings bring one more trap. Double equals asks whether two references point to the same object in memory. Equals asks whether they hold the same content. Here the target is built with new String, so it's a different object from the Ava in the array. The double equals search misses it, and returns minus one. The equals search finds it, at index zero. So compare objects with equals. That's why the linked list search used it.

Technique

The Sentinel Search

The plain loop makes two tests on every pass. Is i still inside the array? And does the cell match? The sentinel technique removes the first test. Save the last element, and overwrite it with the target. Now a match is guaranteed. So the loop runs without checking the end. Afterwards, the last element is restored, and a final test decides what to return. On four, eight, fifteen, sixteen, twenty-three: sixteen is at three, twenty-three at four, and nine isn't there. And the array comes back unchanged.

Quick Check

A Sentinel Without Its Final Test

Quick check. This copy has lost its final test. After restoring the array, it simply returns i. It searches four, eight, fifteen, for nine. What does it print? Pause, and predict. It prints 2. Nine isn't in the array, so the loop runs to the planted copy in the last cell, and stops at index two. Returning i there reports the planted copy as a real match. That's why the real version ends with a test. The stop is genuine only if i is before the last cell, or the saved last value is the target.

Trade-Offs

Counting Tests with a Sentinel

Count the tests for a missing target. On eight elements, the plain loop makes seventeen: nine bounds tests, and eight element tests. The sentinel loop makes eight. On a thousand, it's two thousand and one, against a thousand. That's roughly half, but still in proportion to n, so the search is still linear. And timed on modern Java, it often shows no measurable gain, because the end-of-array test is nearly free. It has risks, too. It changes the data for a moment, so it's unsafe on a read-only array, or one that other code is reading. Forget to restore it, and the array is corrupted. On a linked list, a trailer node can hold the target instead, which is cleaner.

Analysis

Best, Worst, and Average Comparisons

Back to the exam papers. How many looks does a search take? It depends on where the target is, not only on how many there are. This program searches for every element in turn, and averages the counts. Then it tries the first, the last, and a missing value. For ten elements: best case one, worst case ten, absent ten, and five point five on average. That's n plus one, over two. For a thousand, the average is five hundred point five. Double n to two thousand, and every count but the best doubles too.

Key Idea

Linear Time Either Way

So the best case is one comparison, constant. The worst case, n, comes when the target is last, or missing: proving absence means looking everywhere. The average, about half of n, is only a constant factor below the worst case. Half of linear is still linear. A program must be ready for the worst case, so sequential search is described as linear time: O of n.

Decision Guide

When Linear Search Is Best

Linear search has a reputation as the slow one. But in many common cases, it's simply the best tool. Unsorted data has no order to use. A small collection is scanned in a blink. And a one-off lookup doesn't repay sorting first. A linked list can't jump to its middle. A condition, like the first score above 90, has no order to rely on. And changing data needs no upkeep for a scan.

Limitations

Large Data Searched Again and Again

It's the wrong tool for large data searched again and again. A million searches of a million items is up to a trillion comparisons: over sixteen minutes, at a billion a second. And when the data is already sorted, a linear scan ignores free information. Binary search puts that order to work.

Key Takeaways

Sequential Search Essentials

To sum up. Sequential search checks one element at a time, until the target appears, or the data ends. An array moves by index, and a linked list follows its next links, never get of i. Report not found clearly, and check for it. And compare objects with equals. Best case one, worst case n, average about half: linear either way.

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Checking Every Element One at a Time Until the Target Appears

What is linear search in Java?
Linear search, also called sequential search, checks elements one at a time from the start until it finds the target or reaches the end. On an array, the loop for (int i = 0; i < a.length; i++) { if (a[i] == target) return i; } returns the first matching index, and the method returns -1 after the loop if nothing matched. It works on any collection, sorted or not.
What is the time complexity of linear search?
Linear search runs in O(n) time. The best case is one comparison, when the target is first. The worst case is n comparisons, when the target is last or missing, since proving absence means checking every element. If the target is equally likely to be anywhere, the average is (n + 1) / 2 comparisons, which is still proportional to n, so the search is linear either way.
Why use equals instead of == when searching for strings in Java?
Use equals because == checks whether two references point to the same object, while equals compares the strings' content. A target created with new String("Ava") is a different object from the "Ava" stored in an array, so a search using == misses it and returns -1, while a search using equals finds it at index 0. Compare objects with equals in any search.
Why is calling get(i) in a loop slow on a linked list?
Calling get(i) in a loop is slow on a linked list because each get starts at the head and follows i links, creating a hidden loop inside the loop. Searching 10,000 nodes for a missing target this way follows 49,995,000 links, while walking with cur = cur.next takes 10,000 steps. On a linked list, walk node by node instead of indexing.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →