# Sequential Search in Java: Algorithm, Implementation & Analysis

## Sequential Search

Imagine that you have an Excel sheet with 75 rows, and you need to find the value $7.33 within the text. That shouldn't be too hard, right? All you need to do is start scanning down your rows and columns until you find the value. If you find it, you move on. If you don't, you announce that the value is not there.

This type of search is called a **sequential search** (also called a linear search), in which the search starts at the first record and moves through each record until a match is made, or isn't made.

If your worksheet had 500 rows, however, you might want to make use of a search function instead of manually scanning rows and columns. In Java, we can write code to perform a sequential search of our data.

## Sequential Search Algorithm

As stated previously, a sequential search cycles through every element in a data set until a match is found. It's important to re-iterate that every item is checked as the system evaluates the condition.

For a sample sequential search, we're going to use the following assumptions:

- The list or array is
*Q* - We are looking for value
*z* - Our counter is
*i*

The steps of an example search algorithm are listed here, using the previously outlined assumptions:

- Set starting position to first element (
*i*= 0) - If
*i*is greater than the number of elements, go to Step 7 - If
*Q*[*i*] =*z*, then go to Step 6 - Update
*i*to*i*+ 1 - Return to Step 2
- Element
*z*has been found at*i*: Exit (Step 8) - Element Not In List
- Exit Routine

Now that we've walked through how the algorithm works, we can create a Java program that performs a sequential or linear search.

## Implementing the Search in Java

First, let's take a look at an array of data that we will search that's appearing here. Note that sequential searches don't require that the data be sorted.

public class Searches {

public static void main(String[] args) {

//create an array

double[] payments = {3.35, 12.07, 122.76, 7.33, 6.04, 681.78, -0.05, 45.25, 107.33, 6.25, 3.45, 3.45, 0.52};

}

}

Next, we're going to need a method that performs the sequential search. This method accepts two parameters:

- The name of the array
- The key value we are searching for

public static double sequentialSearch(double[] arr, double key) {

int arraySize = arr.length;

for(int i = 0; i < arraySize; i++) {

if(arr[i] == key) {

return i;

}

}

return -1;

}

If the value is not found, the function returns -1. You could return 500 if the array were made up of integers, or ''Fred'' if the array were made of up strings. What is certain is that the code would have to search through every element if the desired value is not in the list.

We're now going to add the searchKey variable and the method call within the main function (right after the array declaration), like you can see appearing here:

//what are we looking for?

double searchKey = 7.33;

System.out.println("Search Key found at: " + sequentialSearch(payments, searchKey));

When the program runs, the output displays:

`Search Key found at: 3.0 `

It's returned as a double since our key value was 7.33.

## Big O Notation

The **Big O Notation** is used to explain performance and complexity of algorithms. In Big O Notation, linear or sequential searches are noted as *O*(*n*), meaning that performance grows at a linear rate with the number of items. When you work with operating systems and multiple processing threads, this becomes important for system performance.

For our small array, or even an array of 500 items, searching isn't very performance heavy. As the array grows, however, so does the horsepower needed to cycle through it. At best, it finds the element fairly quickly. But if the item is at the end of the list, or doesn't exist at all, the process can really take a long time and system performance can be degraded.

In our example from earlier, remember that the processor has to compare the test value (7.33) to every element in the array. So if there are 500 items, it has to walk through 500 times. If there are five million items, that's a really long walk! If 7.33 is at the end of the list, that increases the number of iterations to nearly five million.

The following table appearing here shows the number of comparisons that a program or processor would have to carry out when running a sequential search. This should help clarify the *O*(*n*) notation. Remember that *n* is the count of total elements in the list.

Situation | Best Case | Worst Case | Average |
---|---|---|---|

7.33 is Found | 1 | n |
n/2 |

7.33 is NOT Found | n |
n |
n |

This means that, at worst, the system will have to crunch through every element.

To this point, we used the sequential search on unordered data. But what if the data is sorted? From a processing standpoint, the computer would find 7.33 pretty quickly, and not necessarily need to search through the next four million-plus records. That's a bit more convenient, isn't it?

## Lesson Summary

Let's now take a moment or two to review. As we've learned in this lesson, a **sequential search**, or linear search, is a search that starts at the beginning of an array or list and walks through every element. In computer science, we use the **Big O Notation** to quantify the performance of algorithms in which the linear search is noted as *O*(*n*), meaning performance grows in a linear fashion. At worst, the algorithm has to look at every element. Unfortunately, though, for very large data sets, it can be a performance drag.

To unlock this lesson you must be a Study.com Member.

Create your account

### Register to view this lesson

### Unlock Your Education

#### See for yourself why 30 million people use Study.com

##### Become a Study.com member and start learning now.

Become a MemberAlready a member? Log In

Back### Resources created by teachers for teachers

I would definitely recommend Study.com to my colleagues. It’s like

**a teacher waved a magic wand and did the work for me.** I feel like it’s a lifeline.